How recursive calls use the stack

Overview

Call stack used for during recursion and stack frame.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   What is the call stack used for during recursion?

   Model answer

   The call stack holds one frame for every call that has not yet returned. Each frame stores the return address, the parameters and the local variables.

2. 2

   What is a stack frame?

   Model answer

   A stack frame is the block of memory pushed onto the stack for a single subprogram call. The frame is popped when that call returns.

3. 3

   Why does deep recursion risk a stack overflow?

   Model answer

   The stack has a fixed size and each call adds another frame. Enough unfinished calls will exhaust the space reserved for the stack.

4. 4

   How many stack frames exist at the deepest point of evaluating factorial(5) with base case factorial(0) = 1?

   Model answer

   Six frames exist at the deepest point, one each for 5, 4, 3, 2, 1 and 0. The frames are then removed one at a time as the calls return.

5. 5

   In what order are the recursive calls completed?

   Model answer

   The most recent call is completed first because the stack is last in, first out. The original call is the last to finish.

6. 6

   What is stored in a stack frame besides the local variables?

   Model answer

   The frame stores the return address and the parameters passed to that call. A saved copy of registers may also be kept.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.