Recursion and Memory Visualization

In this section, we will learn how memory is allocated in recursive functions.

We'll cover the following

Memory Allocation in Recursion

When a function is called, its memory is allocated on a stack. Stacks in computing architectures are the regions of memory where data is added or removed in a last-in-first-out (LIFO) process. Each program has a reserved region of memory referred to as its stack. When a function executes, it adds its state data to the top of the stack. When the function exits, this data is removed from the stack.

Suppose we have a program as follows:

def function1(<parameters>) :
  <create some variables>
  return(<some data>)

def function2(<parameters>) :
  <create some variables>
  return(<some data>)

## Driver Code
function1()
function2()

We have created some dummy example and called them in our program. Our memory stack will now look like this:

Illustration of memory stack
Illustration of memory stack

Memory Allocation of Recursive Functions

A recursive function calls itself, so the memory for a called function is allocated on top of the memory allocated for calling the function.

Remember, a different copy of local variables is created for each function call. When the base case is reached, the function returns its value to the function that it was called from, and its memory is de-allocated. This process continues until the parent function is returned.

Calculating Factorial of a Number

Let’s take a look at a recursive function that calculates the factorial of a number.

A factorial is the product of an integer and all the positive integers less than it. A factorial is denoted by the symbol !

For example, 4!4! (read as four factorial) represents the following:

0!=10! = 1

1!=11! = 1

2!=2×1=22! = 2 \times 1 = 2

3!=3×2×1=63! = 3 \times 2 \times 1 = 6

4!=4×3×2×1=244! = 4 \times 3 \times 2 \times 1 = 24

Therefore, if targetNumber=ntargetNumber = n

n!=n×(n−1)×(n−2)×(n−3)×....×(n−(n−1))n! = n \times (n-1) \times (n-2) \times (n-3) \times .... \times (n-(n-1))

Here, the smallest starting value is 1!1!. Therefore, this is our base case.

Notice that some part of the previous task is being replicated in the current task. This is illustrated below:

Let’s take a look at the code:

Press + to interact
 def factorial(targetNumber) :
  # Base case
  if targetNumber == 1 or targetNumber == 0: # Factorial of 1 and 0 is 1
    return 1
  # Recursive case
  else :
    return (targetNumber * factorial(targetNumber - 1)) # Factorial of any other number is
                                                  # number multiplied by factorial of number - 1
# Driver Code
targetNumber = 5
result = factorial(targetNumber)
print("The factorial of " + str(targetNumber) + " is: " + str(result))

Now, let’s visualize the code stack of this code:

For the first 55 iterations call the factorial() function until it is added at the top of the stack, i.e. on top of the previous function call.

Each child function call returns the value to its parent call.

The above sequence represents the sequence of function calls.

In the next lesson, we will be learning two different types of recursion.