Recursion in C++

The principles of recursion are the same, regardless of the language used for implementation. This chapter views the topic through the lens of C++. There are a fair number of examples and visualizations. Read through these at a minimum. You might find the exercises useful since the application of a principle is an aid to your understanding. Read Chapter 5 in this book on C++.

6. Stack Frames: Implementing Recursion

Suppose that instead of concatenating the result of the recursive call to toStr with the string from convertString, we modified our algorithm to push the strings onto a stack instead of making the recursive call. The code for this modified algorithm is shown in ActiveCode 1.

C++
Python

                                                            xxxxxxxxxx
                                                        
 
//Example of the toStr function using a stack instead of recursion.
​
#include <iostream>
#include <string>
#include <stack>
using namespace std;
​
stack<char> rStack;
​
string toStr(int n, int base) {
    string convertString = "0123456789ABCDEF";
    while (n > 0) {
        if (n < base) {
            rStack.push(convertString[n]); //pushes string n to the stack
        } else {
            rStack.push(convertString[n % base]); //pushes string n modulo base to the stack.
        }
        n = n/base;
    }
    string res;
    while (!rStack.empty()) {
        //combines all the items in the stack into a full string.
        res = res + (string(1,  rStack.top()));
        rStack.pop();

Converting an Integer to a String Using a Stack (lst_recstackcpp)

                                                            xxxxxxxxxx
                                                        
 
#Example of the toStr function using a stack instead of recursion.
​
from pythonds.basic.stack import Stack
​
rStack = Stack()
​
def toStr(n,base):
    convertString = "0123456789ABCDEF"
    while n > 0:
        if n < base:
            rStack.push(convertString[n]) #adds string n to the stack.
        else:
            rStack.push(convertString[n % base]) #adds string n modulo base to the stack.
        n = n // base
    res = ""
    while not rStack.isEmpty():
        #combines all the items in the stack to make the full string.
        res = res + str(rStack.pop())
    return res
​
def main():
    print(toStr(1453,16))
​
main()

Converting an Integer to a String Using a Stack (lst_recstackpy)

Each time we make a call to toStr, we push a character on the stack. Returning to the previous example we can see that after the fourth call to toStr the stack would look like Figure 5. Notice that now we can simply pop the characters off the stack and concatenate them into the final result, "1010".

../_images/recstack.png

Figure 5: Strings Placed on the Stack During Conversion

The previous example gives us some insight into how C++ implements a recursive function call. When a function is called in Python, a stack frame is allocated to handle the local variables of the function. When the function returns, the return value is left on top of the stack for the calling function to access. Figure 6 illustrates the call stack after the return statement on line 4.

../_images/newcallstack.png

Figure 6: Call Stack Generated from toStr(10,2)

Notice that the call to toStr(2//2,2) leaves a return value of "1" on the stack. This return value is then used in place of the function call (toStr(1,2)) in the expression "1" + convertString[2%2], which will leave the string "10" on the top of the stack. In this way, the C++ call stack takes the place of the stack we used explicitly in Listing 4. In our list summing example, you can think of the return value on the stack taking the place of an accumulator variable.

The stack frames also provide a scope for the variables used by the function. Even though we are calling the same function over and over, each call creates a new scope for the variables that are local to the function.