Recursion and Memory Visualization

In this lesson, we will learn how memory is allocated for recursive functions.

We'll cover the following

Memory Allocation in Recursion

When a function is called, its memory is allocated on stack. Stacks in computing architectures are regions of memory where data is added or removed in a last-in-first-out (LIFO) manner. 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.

For example, 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 functions and called them in our program. Now our memory stack will look something like this:

Illustration of memory stack
Illustration of memory stack

Memory Allocation of Recursive Functions

A recursive function calls itself, therefore, the memory for a called function is allocated on top of memory allocated for calling 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 from whom it was called and its memory is de-allocated. This process continues until the parent function is returned.

Calculating Factorial of a Number

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

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

For example, 4!4! (read as four factorial) is denoted as follows:

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 we know is 1!1!. Therefore, this is our base case.

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

Let’s have a look at the code:

Press + to interact
 def factorial(targetNumber) :
  # Base case
  if targetNumber == 1 : # Factorial of 1 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 each call to factorial() function is added at the top of the stack, i.e., on top of the previous function call.

Each child function call then 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.