Dry Run of Recursion

Introduction

A recursion dry run means tracing each recursive call and return step manually.

Beginners often understand the code but get confused about what happens after the base case. A dry run solves that confusion.

The safest method is to draw the call stack and separate the calling phase from the returning phase.

Calling phase:
f(4) -> f(3) -> f(2) -> f(1)

Returning phase:
f(1) returns 1
f(2) returns 2
f(3) returns 6
f(4) returns 24

Why Dry Run Matters

How to Dry Run Recursion

The best way to dry run recursion is to write each function call on a new line and track when it returns.

• Write the initial function call.
• Keep expanding recursive calls until the base case.
• Mark the base case return value.
• Return back to previous calls one by one.
• Calculate final answer during the returning phase.

Dry Run Example: factorial(4)

For factorial, the function keeps calling itself with n - 1 until n becomes 1.

Then return values move back upward through the call stack.

• factorial(4) = 4 * factorial(3)
• factorial(3) = 3 * factorial(2)
• factorial(2) = 2 * factorial(1)
• factorial(1) = 1
• Final result = 4 * 3 * 2 * 1 = 24

Call Stack View

The call stack stores active function calls. New calls are pushed on top, and completed calls are popped.

• Push factorial(4).
• Push factorial(3).
• Push factorial(2).
• Push factorial(1).
• Pop calls as values return.

What to Track During Dry Run

A trace table helps when recursion has multiple variables or multiple recursive calls.

• Current function call.
• Current value of parameters.
• Base case condition.
• Return value.
• Pending operation after recursive call.

factorial(4) Trace Table

C Program Example

Dry run this program by tracing factorial(4) from call phase to return phase.

#include <stdio.h>

int fact(int n) {
    if (n == 1) return 1;
    return n * fact(n - 1);
}

int main() {
    printf("%d", fact(4));
    return 0;
}

Output: 24

Key Points

Common Beginner Mistakes

Quick Revision

Summary

A recursion dry run shows exactly how recursive calls are created and resolved. Drawing the call stack is the most reliable way to understand recursive code.