﻿ Recursion - Review the Knowledge You Need to Score High - 5 Steps to a 5 AP Computer Science A 2017 (2016) ﻿

## 5 Steps to a 5 AP Computer Science A 2017 (2016)

### Recursion

IN THIS CONCEPT

Summary: This concept defines and explains recursion. It also shows how to read and trace a recursive method.

Key Ideas

A recursive method is a method that calls itself.

Recursion is not the same as nested for loops or while loops.

A recursive method must have a base case that tells the method to stop calling itself.

You will need to know how to trace recursive methods on the AP Computer Science A Exam. You will not have to write recursive methods.

Recursion Versus Looping

The for loop and the while loop allow the programmer to repeat a set of instructions. Recursion is the process of repeating instructions too, but in a self-similar way. I know that’s kind of weird. Let me explain by using the following example.

Example 1

Imagine you are standing in a really long line and you want to know how many people are in line in front of you, but you can’t see everyone. If you ask the person in front of you how many people are in front of him, and he turns to the person in front of him and asks the person in front of him how many people are in front of him, and so on, eventually this chain reaction will reach the first person in line. This person will turn to the person behind him and say, “No one.” Then something fun happens. The second person in line will turn to the third person and say, “One.” The third person will turn to the fourth person and say, “Two,” and so on, until finally the person in front of you will respond with the number of people who are in front of him. This creative solution to the problem is an example of how a recursive algorithm works.

Recursion is a programming technique that can be used to solve a problem in which a solution to the problem can be found by making subsequently smaller iterations of the same problem. When used correctly, it can be an extremely elegant solution to a problem.

One method can call another method, right? What if the method called itself? If you stop and think about that, after the method was invoked the first time, the program would never end because the method would continue to call itself forever (think of the movie Inception ).

Example 2

Here’s an example of a really bad recursive method.

However, if the method had some kind of trigger that told it when to stop calling itself, then it would be a good recursive method.

General Form for a Recursive Method

Note: All recursive methods must have a base case.

The Base Case

The base case of a recursive method is a comparison between a parameter of the method and a predefined value strategically chosen by the programmer. The base case comparison determines whether or not the method should call itself again. Referring back to the example in the introduction of this concept, the response by the first person in line of “no one” is the base case. It is the answer that reverses the recursive process.

Each time the recursive method calls itself and the base case is not satisfied, the method temporarily sets that call aside before making a new call to itself. This continues until the base case is satisfied. When there is finally a call to the method that makes the base case true (the base case is satisfied), the method stops calling itself and starts the process of returning a value for each of the previous method calls. Since the calls are placed on a stack , the returns are executed in the reverse order of how they were placed. This order is known as last-in, first-out (LIFO), which means that the last recursive call made is the first one to return a value.

Furthermore, each successive call of the method should bring the value of the parameter closer and closer to making the base case true . This means that with each call to the method, the value of the parameter should be closing in on making the base case true rather than moving further away from it being true.

If a recursive method does not contain a valid base case comparison, then it may continue to call itself into oblivion. That would be bad.

What do I mean by bad? Remember that every time a recursive method is called, it has to set that call aside temporarily until the base case is satisfied. This process is called putting the call on the stack and the computer stores this stack in its RAM. If the base case is never satisfied, then the method calls pile up and the computer eventually runs out of memory. This will cause a stack overflow error and it occurs when you have an infinite recursion.

The Base Case

The base case is a comparison between a parameter of the method and some specific predefined value chosen by the programmer. When the base case is true, the method stops calling itself and starts the process of returning values. Every recursive method needs a valid base case or else it will continue to call itself indefinitely (infinite recursion) and cause an out-of-memory error, called a stack overflow error.

Beginner Example: The Factorial Recursive Method

A very popular problem to solve using recursion is the factorial calculation. The factorial of a number uses the notation n! and is calculated by multiplying the integer n by each of the integers that precede it all the way down to 1. Factorial is useful for computing combinations and permutations when doing probability and statistics.

Example

Find the answer to 4! and 10!

4! = 4 * 3 * 2 * 1 = 24. Therefore 4! is 24.

10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 3628800. Therefore, 10! is 3628800.

Why the Factorial Calculation Is a Good Recursive Example

The definition of a factorial can be written recursively. This means that the factorial of the number, n, can use the factorial of the previous number, n – 1, in its computation.

Example

Write 4! recursively using math.

When you start to compute 4! using the definition of factorial, you see that 4! is 4 times 3! This means that in order to compute 4!, you need to figure out what 3! is. But 3! is 3 times 2! so we have to figure out what 2! is. And 2! is 2 times 1!, and 1! is 1.

Do you see how we had to put our calculations on hold until we got to 1!? Once we got a final answer of 1 for 1!, we were able to compute 4! by working backward.

Implementation of the Factorial Recursive Method

On the AP Exam, you will never be asked to write your own original recursive method. However, you will be asked to hand-trace recursive methods and state the results.

Hand-Tracing the Factorial Recursive Method

This is kind of tricky, so read it over very carefully. When tracing a recursive method call, write out each call to the method including its parameter. When the base case is reached, replace the result from each method call with its result, one at a time. This process will force you to calculate the return values in the reverse order from the way that the calls were made.

Goal: Compute the value of factorial(5) using the process of recursion.

Step 1: This problem is similar to the “find the number of people in line” example. The answer to a factorial requires knowledge of the factorial preceding it.

Suppose I ask the number 5, “Hey what’s your factorial?” 5 responds with, “I don’t know. I need to ask 4 what its factorial is before I can find out my own.” Then 4 asks 3 what its factorial is. Then 3 asks 2 what its factorial is. Then 2 asks 1 what its factorial is. Then 1 says, “1”.

Step 2: After 1 says, “1”, the process reverses itself and each number answers the question that was asked of it. The answer of “1” is the base case.

1 says, “My factorial is 1.”

2 then says, “My factorial is 2 because 2 * 1 is 2.”

3 then says, “My factorial is 6 because 3 * 2 is 6.”

4 then says, “My factorial is 24 because 4 * 6 is 24.”

And finally, 5 turns to me and says, “My factorial is 120, because 5 * 24 is 120.”

factorial(1) = 1

factorial(2) = 2 * factorial(1) = 2 * 1 = 2

factorial(3) = 3 * factorial(2) = 3 * 2 = 6

factorial(4) = 4 * factorial(3) = 4 * 6 = 24

factorial(5) = 5 * factorial(4) = 5 * 24 = 120

Conclusion: factorial(5) = 120

A Visual Representation of Computing a Recursive Value

Example

Explain how to compute the value of factorial(5) for the visual learner. As you trace through this problem, think of the original example of the people in the long line.

Advanced Example: The Fibonacci Recursive Method

On the AP Exam, you will need to be able to hand-trace recursive method calls that have either multiple parameters or make multiple calls within the return statement. The following example shows a recursive method that has multiple calls to the recursive method within its return statement.

The Fibonacci Sequence

This popular sequence is often covered in math class as it has some interesting applications. In the Fibonacci sequence, the first two terms are 1, and then each term starting with the third term is equal to the sum of the two previous terms.

1, 1, 2, 3, 5, 8, 13, 21, 34, 55 . . .

The Java code that is provided below is a recursive method that returns the value of the nth term in a Fibonacci sequence. Example: fibonacci(6) is 8. The value of the sixth term is 8.

Hand-Tracing the Fibonacci Recursive Method

This is harder to follow than the factorial recursive method because the return statement includes two calls to the recursive method. Also, there are two base cases.

Goal: Compute the value of fibonacci(6).

Step 1: In a manner similar to the previous example, I ask 6, “What’s your fibonacci?” 6 responds by saying, “I don’t know right now, I need to ask both 5 and 4 what their fibonaccis are.” In response, 5 says, “I need to ask both 4 and 3 what their fibonaccis are.” And, 4 says, “I need to ask both 3 and 2 what their fibonaccis are.” This continues until 2 and 1 are asked what their fibonaccis are.

Step 2: Ultimately 2 and 1 will respond with “1” and “1” and each number can then answer the question that was asked of them. The 2 and 1 are the base cases for this problem.

fibonacci(1) = 1

fibonacci(2) = 1

fibonacci(3) = fibonacci(2) + fibonacci(1) = 1 + 1 = 2

fibonacci(4) = fibonacci(3) + fibonacci(2) = 2 + 1 = 3

fibonacci(5) = fibonacci(4) + fibonacci(3) = 3 + 2 = 5

fibonacci(6) = fibonacci(5) + fibonacci(4) = 5 + 3 = 8

Conclusion: fibonacci(6) is 8

Rapid Review

• Recursive methods are methods that call themselves.
• Choose recursion rather than looping when the problem you are trying to solve can be solved by repeatedly shrinking the problem down to a single, final simple problem.
• Recursive methods usually have a return type (rather than void) and must take a parameter.
• The re-calling of the method should bring you closer to the base case.
• Many problems can be solved without recursion; however, if done properly, recursion can be an extremely elegant way to solve a problem.
• Once the recursive process has started, the only way to end it is to satisfy the base case.
• The base case is a comparison that is done in the method. When this comparison becomes true, the method returns a value that begins the return process.
• If you write a recursive method and forget to put in a base case, or your subsequent calls to the method do not get you closer to the base case, you will probably cause infinite recursion, which will result in a stack overflow error.
• To trace a recursive call, write out each call of the method with the value of the parameter. When the base case is reached, replace each method call with its result. This will happen in reverse order.

Review Questions

Basic Level

1 . Consider the following recursive method.

What value is returned when puzzle(10) is called?

(A)  18

(B)  15

(C)  11

(D)  1

(E)  Nothing is returned. Infinite recursion causes a stack overflow error.

2 .  Consider the following recursive method.

What value is returned when mystery(11) is called?

(A)  1

(B)  49

(C)  73

(D)  665280

(E)  Nothing is returned. Infinite recursion causes a stack overflow error.

3 . Consider the following recursive method.

What value is returned when enigma(9) is called?

(A)  7

(B)  10

(C)  13

(D)  15

(E)  16

4 . Consider the following recursive method.

What will be printed when printStars(15) is called?

(A)  ***************

(B)  *

(C)  Nothing is printed. Method will not compile. Recursive methods cannot print.

(D)  Nothing is printed. Method returns successfully.

(E)  Many stars are printed. Infinite recursion causes a stack overflow error.

5 . Consider the following method.

What value is returned when weird("Hello") is called?

(A)  "Hello"

(B)  "Hellolo"

(C)  "Hellolololo"

(D)  "Hellolololololololo"

(E)  Nothing is returned. Infinite recursion causes a stack overflow error.

Questions 6–7 refer to the following methods.

6 . What value is returned when factors(10) is called?

(A)  0

(B)  1

(C)  2

(D)  3

(E)  4

7 . Which of the following statements will execute successfully?

III.  int answer = factors(12, 2, 5);

(A)  I only

(B)  II only

(C)  III only

(D)  I and II only

(E)  I, II, and III

8 . Consider the following recursive method.

What value is returned when function(24, 3) is called?

(A)  13

(B)  21

(C)  25

(D)  27

(E)  Nothing is returned. Infinite recursion causes a stack overflow error.

9 . Consider this recursive problem.

In elementary school, we learned that if you add up the digits of a number and get a sum of 9, then that number is divisible by 9. If your answer is less than 9, then that number is not divisible by 9. For example,

• 81 8 + 1 = 9, divisible by 9.
• 71 7 + 1 = 8, not divisible by 9.

The trouble is, if you add up the digits of a big number, you get a sum that is greater than 9, for example, 999  9 + 9 + 9 = 27. We can fix this by using the same trick on that sum: 27  2 + 7 = 9, divisible by 9.

Here’s another example:

• 457829 4 + 5 + 7 + 8 + 2 + 9 = 35, keep going,
• 35 3 + 5 = 8, not divisible by 9.

If your number is big enough, you may have to repeat the process three, four, five, or even more times, but eventually, you will get a sum that is < = 9 and that will let you determine whether your number is divisible by 9.

Your client code will call method divisible , passing a number and expecting a boolean result, and divisible will call the recursive method sumUp to

Consider the class below that implements a solution to the problem.

Which of the following can be used to replace /* condition */ and /* argument */ so that sumUp will work as intended?

(A)

(B)

(C)

(D)

(E)

Bullets mark each step in the process of arriving at the correct solution.

1 . The answer is A.

• Let’s trace the calls. The parts initalics were filled in on the way back up. That is, the calls in the plain type were written top to bottom until the base case returned 1. Then the answer were filled in bottom to top .

puzzle(10) = num + puzzle(num/2) = 10 + puzzle(5) = 10 + 8 = 18

puzzle(5) = num + puzzle(num/2) = 5 + puzzle(2) = 5 + 3 = 8

puzzle(2) = num + puzzle(num/2) = 2 + puzzle(1) = 2 + 1 = 3

puzzle(1) = base case! return 1

• Don’t forget to do integer division.

2 . The answer is E.

• Let’s trace the calls just like we did in problem 1.

mystery(11) = 2 * 11 + mystery(9)

mystery(9) = 2 * 9 + mystery(7)

mystery(7) = 2 * 7 + mystery(5)

mystery(5) = 2 * 5 + mystery(3)

mystery(3) = 2 * 3 + mystery(1)

mystery(1) = 2 * 1 + mystery(-1)

Uh oh—the parameter skipped right over 0, and it’s only going to get smaller. This example will recurse until there is a stack overflow error.

• You might be confused by the fact that sometimes people leave out else when writing code like this. Let’s take a look at the code again:

Why doesn’t this have to say else return 2 * k + mystery(k – 2)? The purpose of an else clause is to tell the flow of control to skip that section when the if part is executed. So either the if clause or the else clause is executed. In this case, the if clause contains a return. Once a return is executed, nothing further in the method will be read and control returns to the calling method. We don’t have to tell it to skip the else clause, because it has already gone off to execute code in another method. It doesn’t matter whether you choose to write your code like this or to include the else, but don’t be confused if you see it on the exam.

3 . The answer is C.

• Here we go again!

enigma(9) = 3 + enigma(7) = 3 + 10 = 13

enigma(7) = 3 + enigma(5) = 3 + 7 = 10

enigma(5) = 3 + enigma(3) = 3 + 4 = 7

…here comes one of the base cases!

enigma(3) = 2 + enigma(2) = 2 + 2 = 4

…the other base case!

enigma(2) = 2…and up we go!

4 . The answer is A.

• We don’t really want to trace 15 calls of the printStars method, so let’s see if we can just figure it after a few calls.

printStars(15): prints one * and calls printStars(14)

printStars(14): prints one * and calls printStars(13)

. . .

. . .

printStars(1): prints one * and returns (remember, void methods also return, they just don’t return a value).

• Without tracing every single call, we can see the pattern. 15 stars will be printed.
• This recursive method is a little different because it is not a return method. That’s allowed, but it is not very common.

5 . The answer is C.

• This time with Strings!

weird("Hello") = weird("Hello" + "lo") = weird("Hellolo") = "Hellolololo"

weird("Hellolo") = weird("Hellolo" + "lo") = weird("Hellololo") = "Hellolololo"

weird("Hellololo") = weird("Hellololo" + "lo") = weird("Hellolololo") = "Hellolololo"

. . . that has a length >10, so we just start returning s.

• This one is a little different because there is no computation on the “return trip.”

6 . The answer is C.

• Instead of tracing the code, this time we are going to reason out what the method is doing.
• Notice that factors is an overloaded method. Our first call has one int parameter, but the remaining calls all have three. Our first call, factors(10), will result in the call factors(10, 9, 0).
• Looking at the factors method with three parameters, we can see that each time through, we subtract one from check, and the base case is check = = 1. We start with check = 9 and call the method eight more times before returning count. Count begins at 0 and will be incremented when number % check = = 0. Since number is 10, and check will equal all the numbers between 1 and 9, that will happen twice, at 10 % 5 and at 10 % 1. When the return statement is reached, count = 2.

7 . The answer is C.

• Option I is incorrect. factors(0) will call factors(0, -1, 0). Since check is decremented each time, we will move further and further from the base case of 1. Infinite recursion will result in a stack overflow exception.
• Option II is incorrect. factors(2) will call factors(2, 1, 0). Since check is decremented to 0 before checking for the base case, once again we have infinite recursion resulting in a stack overflow error.
• Option III is correct. factors(12, 2, 5) will increment count (12 % 2 = = 0), decrement check to 1, and then check for the base case and return count.

8 . The answer is B.

• Let’s trace.

function(24, 3) = function(21, 4) + 2 = 19 + 2 = 21

function(21, 4) = function(17, 5) + 2 = 17 + 2 = 19

function(17, 5) = function(12, 6) + 2 = 15 + 2 = 17

function(12, 6) = function(6, 7) + 2 = 13 + 2 = 15

function(6, 7) = 6 + 7 = 13 (base case!)

9 . The answer is A.

• The if statement we are completing represents the base case and the recursive call.
• We need to keep going if sum > 9, so the base case, the case that says we are done, occurs at sum < 9. That is thecondition . If sum < 9, all we need to do is return sum.
• If sum >= 9, we need to add the digits up again, but the question is, the digits ofwhat ? If you go back to the examples in the description, 999, for example, the while loop will add 9 + 9 + 9 and put the result in sum, which now = 27. Then the next step is to add 2 + 7. Since 27 is held in the variable sum, that’s what we need to pass to the next round of recursion. The argument is sum.
• You don’t need to understand the while loop to answer the question, but it is a pretty cool loop, so let’s explain it here anyway.
• dividend % 10 gives you the last digit of dividend
• dividend / 10 gets rid of the last digit of dividend (because it is integer division)
• Here’s an example, using the number is 365.

365 / 10 = 36 remainder 5 (mod will give us 5, add it to sum)

36 / 10 = 3 remainder 6 (mod will give us 6, add it to sum)

3 / 10 = 0 remainder 3 (mod will give us 3, add it to sum)

0 will cause the loop to terminate.

﻿