Section 24.10 Multiple Recursive Calls
It is possible to make multiple recursive calls within a function. This is often used to solve problems via divide and conquer strategy. Divide and conquer means breaking a problem down into smaller, similar sub-problems, solving those sub-problems, and then combining the results to solve the original problem. This kind of problem is where recursion really shines as divide and conquer is a natural fit for a recursive design.
For example, consider the task of generating all binary strings of a given length. A binary string is a string that only contains 0s and 1s. Given a particular binary string, like
011, if we want to add one more bit to the end of it, we have two options: we can add a 0 or we can add a 1. So from 011, we can generate 0110 and 0111. Then we can take both of those strings and add a 0 or a 1 to the end of them.
To will design this as a tail recursive function where we pass “the string so far” to each level of recursion along with “how many more bits to add”. That choice implies that the base case will be when there are no more bits to add.
- What are the inputs/outputs
- Takes string built so far and number of remaining bits to add. Returns nothing.
- What is the base case
- Remaining bits is 0. Print the current string.
- What is the recursive case
- Make two recursive calls, one where we add a 0 to the current string and one where we add a 1 to the current string. In each call, there will be one fewer remaining bit to add.
Below is an implementation of our function:
From an input of 3, we end up with 8 lines of output. This is because each recursive call produces two new calls:
printBinaryStrings(3)The actual order these calls are made is determined by the order of the recursive calls in the code. In our implementation, we first make the call that adds a 0 and then we make the call that adds a 1. So, we will first generate all the strings that start with 0 and then we will generate all the strings that start with 1.
The next level down makes the same decision: it first generates all the strings that start with 0 and then all the strings that start with 1. This pattern continues until we reach the base case.
So the process looks like:
-
We return to
printBinaryStrings("00", 1). It is done printing 0’s, so it now callsprintBinaryStrings("001", 0)to print ones. -
We return to
printBinaryStrings("00", 1). It is done printing 1’s, so it returns. -
We return to
printBinaryStrings("0", 2). It is done printing 0’s, so it now callsprintBinaryStrings("01", 1) -
...
We keep drilling down the left branch (zero branch) until we bottom out. Then we back track to somewhere where we have yet to do the right branch (one branch) and do a recursive call there. To change the order of the output, you can simply swap the order of the recursive calls in the code. That will force the right branch to be explored first.
You have attempted of activities on this page.
