Recursion
Skill 3.CSkill 4.ASkill 4.B
Big idea: A recursive method solves a problem by calling itself on a smaller version of it, until it reaches a base case simple enough to answer directly.
- Determine the result of calling recursive methods.
Base case and recursive call
Every recursive method needs a base case that returns without recursing, and a recursive call that moves toward it. Without that, it recurses forever and crashes with a StackOverflowError.
static int fact(int n) {
if (n <= 1) return 1; // base case
return n * fact(n - 1); // recursive call on a smaller n
}System.out.println(fact(5));120Tracing: write the calls down
Write each call on its own line, go down to the base case, then substitute the results back up:
Methodsstatic int fact(int n) {
if (n <= 1) return 1;
return n * fact(n - 1);
}// fact(4) = 4 * fact(3)
// = 4 * (3 * fact(2))
// = 4 * (3 * (2 * fact(1)))
// = 4 * (3 * (2 * 1)) = 24
System.out.println(fact(4));24Work before vs. after the call
Code before the recursive call runs on the way down; code after it runs on the way back up, in reverse order.
Methodsstatic void down(int n) {
if (n == 0) return;
System.out.print(n + " ");
down(n - 1);
}
static void up(int n) {
if (n == 0) return;
up(n - 1);
System.out.print(n + " ");
}down(3);
System.out.println();
up(3);
System.out.println();3 2 1 1 2 3
Recursion on strings
Methodsstatic String reverse(String s) {
if (s.length() <= 1) return s;
return reverse(s.substring(1)) + s.substring(0, 1);
}
static int countX(String s) {
if (s.length() == 0) return 0;
int first = 0;
if (s.substring(0, 1).equals("x")) first = 1;
return first + countX(s.substring(1));
}System.out.println(reverse("abc"));
System.out.println(countX("xaxbx"));cba 3
- A recursive method calls itself. It needs a base case and a recursive call that moves toward it.
- Each call has its own parameters and local variables.
- Any recursive solution can be written iteratively, and vice versa.
- Trace with a stack of calls on paper. Output printed after the recursive call comes out in reverse order.
- A missing or unreachable base case means infinite recursion.
What does mystery(4) return?
int mystery(int n) {
if (n == 0) return 0;
return n + mystery(n - 1);
}Show answer
10 (4 + 3 + 2 + 1 + 0).
- Writing recursive code. You only need to trace it.