11.1.1. What is Recursion?¶
Recursion is when a method calls itself. See the example method below.
1public static void neverEnd()
2{
3 System.out.println("This is the method that never ends!");
4 neverEnd();
5}
This method will print out “This is the method that never ends!” and then call itself, which will print out the message again, and then call itself, and so on. This is called infinite recursion, which is a recursion that never ends. Of course, this particular method is not very useful.
Check your Understanding
- Yes
- Where is the call to the same method?
- No
- There is no call to the same method, so this can not be a recursive method. It uses iteration instead.
11-1-2: Is the following method recursive?
1public static int mystery() 2{ 3 int total = 0; 4 for (int i=10; i>0; i--) 5 { 6 total = total + i; 7 } 8 return total; 9}
- Yes
- Yes, any method that contains at least one call to the same method is recursive.
- No
- Look again. Check if the method contains a call to itself.
11-1-3: Is the following method recursive?
1public static int mystery2(int x) 2{ 3 if (x == 1) return 1; 4 else return x + mystery2(x-1); 5}
11.1.2. Why use Recursion?¶
Recursion is most useful when it is used to solve problems where the structure of the problem repeats. For example, what if you wanted to find out how much space a folder on your computers uses? You could add up the sizes of all the files in that folder, but folders can also contain subfolders. So you will have to repeat the procedure (method) for each subfolder. Each subfolder can also contain subfolders.
Recursion can also be used to create fractals. A simple example is Sierpinski’s triangle in which you subdivide a triangle into 4 new triangles as shown below. You can then do the some procedure with each new triangle except the center one.
Figure 1: A sequence of Sierpinski’s triangles¶
Recursion can also be used to traverse String, array, and ArrayList objects, much like a loop. In fact, any recursive solution could be written with iteration (loops) instead.
11.1.3. Factorial Method¶
The following video is also on YouTube at https://youtu.be/V2S_8E_ubBY. It introduces the concept of recursion and tracing recursion with the factorial method.
See the method factorial below that calculates the factorial of a number. The factorial of a number is defined as 1 for 0 and n * factorial (n-1) for any other number.
1public static int factorial(int n)
2{
3 if (n == 0)
4 return 1;
5 else
6 return n * factorial(n-1);
7}
Check your understanding
Coding Exercise
Run the code below to test the factorial method. What’s the factorial of 6? Add another test to print out the factorial of 6. What’s the factorial of 1? Add another test to print out the factorial of 1.
11.1.4. Base Case¶
Every recursive method must have at least one base case which halts the recursion. This is usually an if statement that causes the recursion to stop by just giving an answer without needing a recursive method call. You could also think of it as the simplest case where you can give the answer right away. The factorial method has a way to stop the recursion (not call itself). It stops when n is equal to 0, since it just returns 1. This is the base case.
Note
The thing that stops a recursive method from calling itself is called the base case. A method can have more than one base case (way to stop the recursion).
Check your understanding
public static int factorial(int n) { if (n == 0) return 1; else return n * factorial(n-1); }
- 0
- Look again. What is the value of n when this method returns a value, without doing a recursive call?
- 1
- This method stops calling itself when n equals 1 (line 3).
- 2
- Look for a return with a number after it. When is this code executed?
11-1-8: What is the value of n when this method stops calling itself (when it reaches the base case)?
1public static int product(int n) 2{ 3 if(n == 1) 4 return 1; 5 else 6 return n * product(n - 2); 7}
- 0
- This method also stops for another value of n.
- 1
- This method also stops for another value of n.
- Both 0 and 1
- This method stops calling itself when n is either 0 or 1.
11-1-9: What is/are the values of the variable bunnies when this method stops calling itself (when it reaches the base case)?
1public static int bunnyEars(int bunnies) 2{ 3 if (bunnies == 0) return 0; 4 else if (bunnies == 1) return 2; 5 else return 2 + bunnyEars(bunnies - 1); 6}
- yes
- Where is the call to the same method?
- no
- There is no call to the same method, so it is not recursive. This uses iteration instead.
11-1-10: Is the following method recursive?
1public static int bunnyEars(int bunnies) 2{ 3 int total = 0; 4 for (int i = 0; i < bunnies; i++) 5 { 6 total = total + 2; 7 } 8 return total; 9}
Continue to the next page for Day 2 of the Recursion lesson.