11.1.6. 
Tracing Challenge : Recursion¶
Trace through the following recursion problems.
Consider the following recursive method:
1public static int mystery(int n)
2{
3 if (n == 0)
4 return 1;
5 else
6 return 3 * mystery (n - 1);
7}
The trace of this code for mystery(4) is shown below.
mystery(4) returns 3 * mystery(3)
mystery(3) returns 3 * mystery(2)
mystery(2) returns 3 * mystery(1)
mystery(1) returns 3 * mystery(0)
mystery(0) returns A
Before you keep reading...
Making great stuff takes time and $$. If you appreciate the book you are reading now and want to keep quality materials free for other students please consider a donation to Runestone Academy. We ask that you consider a $10 donation, but if you can give more thats great, if $10 is too much for your budget we would be happy with whatever you can afford as a show of support.
Once mystery(0) returns 1 the value for each call to mystery can now be calculated and returned.
mystery(4) returns 3 * mystery(3) = 3 * X = Y
mystery(3) returns 3 * mystery(2) = 3 * 9 = 27
mystery(2) returns 3 * mystery(1) = 3 * 3 = 9
mystery(1) returns 3 * mystery(0) = 3 * 1 = 3
mystery(0) returns 1
Consider the following recursive method:
1public static int strMethod(String str)
2{
3 if (str.length() == 1) return 0;
4 else
5 {
6 if (str.substring(0,1).equals("e")) return 1 +
7 strMethod(str.substring(1));
8 else return strMethod(str.substring(1));
9 }
10}
strMethod("every") returns 1 + strMethod("very")
strMethod("very") returns strMethod("ery")
strMethod("ery") returns 1 + strMethod("ry")
strMethod("ry") returns strMethod("y")
strMethod("y") returns B
Once strMethod(“y”) returns, the value from each recursive call on the stack can be calculated and returned.
strMethod("every") returns 1 + strMethod("very") = Z
strMethod("very") returns strMethod("ery") = Y
strMethod("ery") returns 1 + strMethod("ry") = 1 + X
strMethod("ry") returns strMethod("y") = 0
strMethod("y") returns 0
11.1.7. Summary¶
A recursive method is a method that calls itself.
Recursive methods contain at least one base case, which halts the recursion, and at least one recursive call.
Each recursive call has its own set of local variables, including the formal parameters.
Parameter values capture the progress of a recursive process, much like loop control variable values capture the progress of a loop.
Any recursive solution can be replicated through the use of an iterative approach.
Writing recursive program code is outside the scope of the course and AP Exam.
Recursion can be used to traverse String, array, and ArrayList objects.