6.3. Stack Diagrams for Recursive Functions

In the previous chapter we used a stack diagram to represent the state of a program during a function call. The same kind of diagram can make it easier to interpret a recursive function.

Remember that every time a function gets called it creates a new instance that contains the function’s local variables and parameters.

This figure shows a stack diagram for countdown, called with n = 3:

There is one instance of main and four instances of countdown, each with a different value for the parameter n. The top of the stack, countdown with n = 0 is the base case. It does not make a recursive call, so there are no more instances of countdown.

Note

Does the stack grow upward or downward?

Actually, it’s implementation defined. But on any given platform, stack growth is consistent. It can’t grow ‘up’ one day and ‘down’ the next.

We normally think of a stack like a physical stack of plates with the most recent item on the top. When the stack grows ‘down’ then the most recent item appears visually on the bottom. Slightly confusing, but they are drawn this way in the book to be consistent with the stack visualizations in codelens.

The instance of main is calls countdown, but does not have any parameters or local variables.

Try This!

Draw a stack diagram for print_lines, invoked with the parameter n = 4.

Q-1: Refer to the print_lines function below. It is the same as the print_lines function defined on the previous page. How many instances of print_lines would there be in the stack diagram if we begin with n = 4?

void print_lines(int n) {
  if (n > 0) {
    cout << endl;
    print_lines(n + 1);
  }
}

• 3
• If print_lines could reach its base case, it cannot be done in 3 function calls.
• 4
• If print_lines could reach its base case, it cannot be done in 4 function calls.
• 5
• If print_lines could reach its base case, it could be done in 5 function calls, but does it ever reach the base case?
• infinite
• The print_lines function never reaches its base case, so the stack diagram would be infinitely long.

You have attempted of activities on this page