Insight 21.5.1.
Return values and parameters are how you track state in recursion. Any variable you would build up using a loop needs to get turned into parameters or return values in a recursive function.
Section 21.5 Designing Recursive Functions
Recursion and iteration (loops) are two different approaches to repeat the same instructions multiple times. Any problem that can be solved with one approach can also be solved with the other, although the solutions may look quite different. For problems that are naturally recursive, it is likely the recursive version will produce a simpler and more elegant solution.
Designing recursive algorithms requires thinking in a different way than solving with a loop. When using a loop, we typically track some information in variables as we iterate through the steps. At each step, we update that information to build an answer.
Consider this function to sum up the digits in an integer:
The information we keep track of are the variables
sum and n. Each step of the loop adds the last digit to sum and then removes the last digit from n.
In recursion, there is no loop, so we can’t keep track of information in the same way. The job of adding each digit to the sum will be split across many different function calls. They way we will keep track of information is by either passing or returning it from one recursive call to the next.
The input for the loop-based function is
n. Each recursive call will change n before making a new recursive call. The result of the loop-based function is sum. That is what we will have to return in our recursive implementation.
Next, we need to identify a base case. That will be a situation where there is no reasonable way to make the problem any simpler. A situation where the answer can be determined without worrying about multiple steps.
What is a situation where
addDigits can easily identify the answer? Well, if there is only one digit (the number is less than 10), than the sum of the digits is simply the number itself. It doesn’t get much simpler than that!
int addDigits(int n) {
if (n < 10) {
return n; // base case: single digit
} else {
// recursive case: more than one digit
int sum = 0; ???
return sum;
}
}
Now we need to figure out how to handle the recursive case. The job of a recursive case is NEVER to solve the entire problem. It is to break the problem down into smaller pieces and say “if someone solves that smaller problem for me, I can tell you the answer to the full problem”.
Imagine you are in charge of adding the digits in a number. You are given a long number like
54324238. If you had an assistant to help you might ask them to add all the digits except the last one. “Hey - tell me what the sum of 5432423 is!”. Once they told you their answer, you could add the first digit, 8, to that sum to get the final result.
Put that way, your job just became easy. You don’t care if the number is
548 or 54378573984579384758. You will hand off everything but the last digit and wait for a response. Once you get that response, you will add 8 to it to determine your answer.
Insight 21.5.2.
Recursive cases always say something like “I don’t know the answer, but if someone tells me the answer to this slightly simpler problem, I could easily figure out my answer”.
So our recursive case for adding digits involves looking at the last digit, making a recursive call using everything but that digit, and then adding the last digit to the result of that call:
int addDigits(int n) {
if (n < 10) {
return n; // base case: single digit
} else {
int lastDigit = n % 10; // get the last digit
int remainingDigits = n / 10; // remove the last digit
int nextSum = addDigits(remainingDigits); // recursive call
int sum = nextSum + lastDigit; // add last digit to the response
return sum;
}
}
The way that the recursive case breaks down the problem into something slightly simpler should get us closer and closer to a base case. That is what will eventually end the recursion! This is the case for our solution. At each recursive call, the number we are working with gets one digit shorter. Eventually, it is only one digit and falls into the base case. Try running the program in a Codelens to see:
Wait, weren’t we promised that recursion could sometimes produce simpler and easier algorithms? That version of the algorithm intentionally stores every value that is calculated so we can watch the code run. Once we are confident in how the code works, we could rewrite it to be this version:
To summarize our process:
-
Identify the inputs and outputs for the function
-
Determine the base case for the recursion
-
Define the recursive case to break down the problem into a smaller version that is one step closer to the base case
Checkpoint 21.5.1.
We want to write a recursive function
int letterCount(string s) that counts the number of letters in a string. (We are not allowed to use .size() to help us.) What might be a good base case?
- There is only one letter in the string.
- How would you know that without using
.size()? - The string is
== "". - There are only two letters in the string.
- How would you know that without using
.size()?
Checkpoint 21.5.2.
We want to write a recursive function
int letterCount(string s) that counts the number of letters in a string. (We are not allowed to use .size() to help us.) How could recursion get one step closer to the base case?
- Chop the string in half.
- How would you determine the halfway point?
- Remove one letter from the string.
- Remove all but the first letter from the string.
- That sounds like more than one step towards the base case.
Checkpoint 21.5.3.
We want to write a recursive function
int letterCount(string s) that counts the number of letters in a string. (We are not allowed to use .size() to help us.) How could the recursive case determine its answer?
- The count produced by the recursive call
- That means each recursive call would produce the same answer. (Whatever the base case produces.)
- 1 + the count produced by the recursive call
- 1
- That would ignore the results of recursion.
You have attempted of activities on this page.
