10.1.6.
Tracing Challenge : Recursion¶
Working in pairs, trace through the following recursion problems.
Consider the following recursive method:
1public static int mystery(int n)
2{
3 if (n == 0)
4 {
5 return 1;
6 }
7 else
8 {
9 return 3 * mystery (n - 1);
10 }
11}
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
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
Before you keep reading...
Runestone Academy can only continue if we get support from individuals like you. As a student you are well aware of the high cost of textbooks. Our mission is to provide great books to you for free, but we ask that you consider a $10 donation, more if you can or less if $10 is a burden.
Consider the following recursive method:
1public static int strMethod(String str)
2{
3 if (str.length() == 1)
4 {
5 return 0;
6 }
7 else
8 {
9 if (str.substring(0,1).equals("e"))
10 {
11 return 1 + strMethod(str.substring(1));
12 }
13 else
14 {
15 return strMethod(str.substring(1));
16 }
17 }
18}
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
10.1.7. Summary¶
A recursive method is a method that calls itself.
Recursive methods that don’t recurse infinitely must contain at least one base case when the method can return an answer immediately.
Each recursive call, like any method call, has its own set of local variables, including its parameters.
Parameter values capture the progress of a recursive process, much like loop variable values capture the progress of a loop.
Any iterative procedure can be implemented with recursion but may run into limitations on how deep the call stack can get.
Some recursive procedures can only be translated into iterative code by using extra data structures to keep track of information that is implicit in the structure of recursive calls in recursive code.
Writing recursive program code is outside the scope of the course and AP Exam.
Recursion can be used to traverse
String
s, arrays, andArrayList
s.