How Recursive Calls Work

1. How Recursive Calls Work

When a recursive function is called, the current state of the function (parameter values, local variables, etc.) is saved onto the stack, and control moves to the newly called function. Then, the function completes its execution in reverse order, starting with the most recently called function, as it is removed from the stack.

Since the stack operates on a LIFO (Last In, First Out) basis, recursive calls first "go deep" (forward process) and then "return backward" (backward process).

---

2. The Forward Process

The forward process occurs when the recursive function calls itself, diving deeper into the recursion. At this point, execution pauses at the current function and moves to the next call.

For example, consider the following code:

def example(n):
    if n == 0:
        return
    print("Forward:", n)
    example(n - 1)
    print("Backward:", n)

Execution Flow:

1. example(3) is called → prints: Forward: 3 → calls example(2)

2. example(2) is called → prints: Forward: 2 → calls example(1)

3. example(1) is called → prints: Forward: 1 → calls example(0)

4. example(0) meets the base case (n == 0), so it returns.

---

3. The Backward Process

When the base case is reached, no further recursive calls are made. Now, the stack starts unwinding, and each function is removed one by one as control returns to the previous calls.

Execution Flow (continued):

1. From example(0) → returns to example(1) → prints: Backward: 1

2. From example(1) → returns to example(2) → prints: Backward: 2

3. From example(2) → returns to example(3) → prints: Backward: 3

Final Output:

Forward: 3
Forward: 2
Forward: 1
Backward: 1
Backward: 2
Backward: 3

---

4. Application of Forward and Backward Processes

The forward and backward processes can be used to control the order of outputs, depending on where the code is executed.

For example, to print numbers in the following pattern:

• From N to 1 during the forward process

• From 1 to N during the backward process

You can write:

def print_numbers(N):
    if N == 0:
        return
    print(N, end=" ")  # Forward process
    print_numbers(N - 1)  # Recursive call (go deeper)
    print(N, end=" ")  # Backward process

Execution Flow (N = 3):

Forward process:

1. print(3) → calls print_numbers(2)

2. print(2) → calls print_numbers(1)

3. print(1) → calls print_numbers(0) → returns

Backward process:

1. Returns to print_numbers(1) → print(1)

2. Returns to print_numbers(2) → print(2)

3. Returns to print_numbers(3) → print(3)

Final Output:

3 2 1 1 2 3

---

5. Summary

• Forward process: Executes code before or during the recursive call (dives deeper into the recursion).

• Backward process: Executes code as the function returns (when the stack unwinds).