Algorithms 101: Understanding Recursion with a Deep Dive into the Call Stack

Introduction

In this blog post, we’ll explore the concept of recursion and how it interacts with the call stack, which is fundamental to understanding how recursive functions execute. We’ll provide practical examples in both Python and JavaScript to help solidify these concepts. By the end of this post, you should have a thorough understanding of recursion and the call stack.

What is Recursion?

Recursion occurs when a function calls itself directly or indirectly. The two main types of recursion are:

• Direct Recursion: A function calls itself.
• Indirect Recursion: Two or more functions call each other in a loop.

Recursion is a powerful technique for solving problems that can be broken down into smaller, similar sub-problems.

Why Learn Recursion?

Recursion can be challenging, but it is essential for solving certain types of problems effectively. It is particularly useful for tasks such as:

• Navigating hierarchical data structures (e.g., trees, graphs)
• Performing complex searches (e.g., backtracking algorithms)
• Implementing algorithms for problems that have a recursive nature (e.g., Fibonacci sequence, factorial)

The Call Stack

To understand recursion deeply, we need to understand the call stack. The call stack is a data structure used by the program to keep track of function calls. When a function is called, a new frame is added to the stack. This frame contains the function’s arguments, local variables, and the return address.

How the Call Stack Works

1. Function Call: When a function is called, a new stack frame is pushed onto the stack.
2. Function Execution: The function executes, and if it makes another function call, a new frame is pushed onto the stack.
3. Function Return: When a function completes, its frame is popped from the stack, and control returns to the calling function.

Each recursive call adds a new frame to the stack, and these frames are popped off in the reverse order of their addition.

Example 1: Fibonacci Sequence

Python Example

Let’s calculate the Fibonacci number for n = 4 and visualize the stack frames.

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(4))  # Output: 3

JavaScript Example

Here’s the same example in JavaScript:

function fibonacci(n) {
    if (n === 0) {
        return 0;
    } else if (n === 1) {
        return 1;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

console.log(fibonacci(4));  // Output: 3

Explanation with Call Stack

For fibonacci(4), the call stack evolves as follows:

1. fibonacci(4) is called.
   • Stack: [fibonacci(4)]
2. fibonacci(3) and fibonacci(2) are called.
   • Stack: [fibonacci(4), fibonacci(3)]
   • Stack: [fibonacci(4), fibonacci(3), fibonacci(2)]
3. fibonacci(2) calls fibonacci(1) and fibonacci(0).
   • Stack: [fibonacci(4), fibonacci(3), fibonacci(2), fibonacci(1)]
   • Stack: [fibonacci(4), fibonacci(3), fibonacci(2), fibonacci(0)]
4. Base cases fibonacci(1) and fibonacci(0) return 1 and 0, respectively.
   • Stack after fibonacci(1): [fibonacci(4), fibonacci(3), fibonacci(2)]
   • Stack after fibonacci(0): [fibonacci(4), fibonacci(3), fibonacci(2)]
5. fibonacci(2) returns 1 (1 + 0).
   • Stack: [fibonacci(4), fibonacci(3)]
6. fibonacci(3) calls fibonacci(2) again and fibonacci(1).
   • Stack: [fibonacci(4), fibonacci(3), fibonacci(2)]
   • Stack: [fibonacci(4), fibonacci(3), fibonacci(1)]
7. Base case fibonacci(1) returns 1.
   • Stack: [fibonacci(4), fibonacci(3)]
8. fibonacci(3) returns 2 (1 + 1).
   • Stack: [fibonacci(4)]
9. Finally, fibonacci(4) returns 3 (2 + 1).
   • Stack: []

Example 2: Factorial

Python Example

Let’s calculate the factorial of n = 5.

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)

print(factorial(5))  # Output: 120

JavaScript Example

Here’s the same example in JavaScript:

function factorial(n) {
    if (n === 1) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

console.log(factorial(5));  // Output: 120

Explanation with Call Stack

For factorial(5), the call stack evolves as follows:

1. factorial(5) is called.
   • Stack: [factorial(5)]
2. factorial(4) is called.
   • Stack: [factorial(5), factorial(4)]
3. factorial(3) is called.
   • Stack: [factorial(5), factorial(4), factorial(3)]
4. factorial(2) is called.
   • Stack: [factorial(5), factorial(4), factorial(3), factorial(2)]
5. factorial(1) is called.
   • Stack: [factorial(5), factorial(4), factorial(3), factorial(2), factorial(1)]
6. Base case factorial(1) returns 1.
   • Stack: [factorial(5), factorial(4), factorial(3), factorial(2)]
7. factorial(2) returns 2 (2 * 1).
   • Stack: [factorial(5), factorial(4), factorial(3)]
8. factorial(3) returns 6 (3 * 2).
   • Stack: [factorial(5), factorial(4)]
9. factorial(4) returns 24 (4 * 6).
   • Stack: [factorial(5)]
10. Finally, factorial(5) returns 120 (5 * 24).
    • Stack: []

Example 3: Reversing a Linked List

Python Example

Let’s reverse a linked list recursively.

class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

def reverse_linked_list(head):
    if head is None or head.next is None:
        return head
    p = reverse_linked_list(head.next)
    head.next.next = head
    head.next = None
    return p

# Creating a linked list 1 -> 2 -> 3 -> 4
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
new_head = reverse_linked_list(head)

# Printing the reversed linked list
while new_head:
    print(new_head.value, end=" ")  # Output: 4 3 2 1
    new_head = new_head.next

JavaScript Example

Here’s the same example in JavaScript:

class ListNode {
    constructor(value = 0, next = null) {
        this.value = value;
        this.next = next;
    }
}

function reverseLinkedList(head) {
    if (head === null || head.next === null) {
        return head;
    }
    const p = reverseLinkedList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}

// Creating a linked list 1 -> 2 -> 3 -> 4
const head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4))));
let newHead = reverseLinkedList(head);

// Printing the reversed linked list
while (newHead) {
    console.log(newHead.value);  // Output: 4 3 2 1
    newHead = newHead.next;
}

Explanation with Call Stack

For reversing a linked list 1 -> 2 -> 3 -> 4, the call stack evolves as follows:

1. reverseLinkedList(1) is called.
   • Stack: [reverseLinkedList(1)]
2. reverseLinkedList(2) is called.
   • Stack: [reverseLinkedList(1), reverseLinkedList(2)]
3. reverseLinkedList(3) is called.
   • Stack: [reverseLinkedList(1), reverseLinkedList(2), reverseLinkedList(3)]
4. reverseLinkedList(4) is called.
   • Stack: [reverseLinkedList(1), reverseLinkedList(2), reverseLinkedList(3), reverseLinkedList(4)]
5. Base case `reverseLinked

List(4)` returns 4.

• Stack: [reverseLinkedList(1), reverseLinkedList(2), reverseLinkedList(3)]
  6. Adjust pointers: reverseLinkedList(3) sets 3.next.next = 3 and 3.next = null.
• Stack: [reverseLinkedList(1), reverseLinkedList(2)]
  7. Adjust pointers: reverseLinkedList(2) sets 2.next.next = 2 and 2.next = null.
• Stack: [reverseLinkedList(1)]
  8. Adjust pointers: reverseLinkedList(1) sets 1.next.next = 1 and 1.next = null.
• Stack: []

The list is now reversed: 4 -> 3 -> 2 -> 1.

Summary

Understanding recursion deeply requires a good grasp of the call stack and how it manages function calls. By visualizing the call stack, we can better understand the flow of recursive functions and how they solve problems. Practice with examples like the Fibonacci sequence, factorial, and reversing a linked list to strengthen your understanding.

Tips for Understanding Recursive Code

1. Draw the Call Stack: Visualize the function calls and base cases.
2. Track Variables: Keep a detailed record of the variable values at each step.
3. Identify Base Cases: Understand the conditions under which the recursion stops.
4. Follow the Execution Order: Remember that the order of operations in recursive functions can differ from linear code.