Recursion and Memory Visualization

In this lesson, we'll 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 the stack. Stacks in computing architectures are regions of memory where data is added or removed in a last-in-first-out (LIFO) manner, where the last element that is pushed is also the first element that is removed.

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:

function function1(<parameters>) {
  <create some variables>
  return <some data>;
}

function function2(<parameters>) {
  <create some variables>
  return <some data>;
}

// Driver Code
function1();
function2();

We’ve created some dummy functions and called them in our program. Now our memory stack will look something like this:

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 child function returns its value to the function from which it was called. Then, this child function’s stack frame is removed. This process continues until the parent function is returned.

Let’s try to understand how this works with the help of an example.

Calculating the 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: 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)×....×1n! = n \times (n-1) \times (n-2) \times .... \times 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. For example for calculating 4!4! we do 4×3!4 \times 3!. Now, calculating 3!3! is a subtask of 4!4!.

We can write the mathematical formula recursively as:

n!={1                            if n<=1,n×(n−1)!      if n>1n! = \begin{cases} 1\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\: if \:n <= 1, \\ n \times (n-1)! \:\:\:\:\:\: if \:n > 1 \end{cases}

Let’s have a look at an illustration:

This can be mapped on to the following code:

function 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
var targetNumber = 5;
var result = factorial(targetNumber);
console.log("The factorial of " + targetNumber + " is: " + result);

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

For the first 44 recursive calls, each call to factorial() function is added at the top of the stack, i.e., on top of the previous function call. For the last recursive call, the base case is satisfied and therefore, 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 about two different types of recursion.