Recursion

🧠 Understanding Recursion in Python with Factorial Example

Recursion is one of those magical concepts in programming that might look confusing at first—but once you understand how the function calls itself, everything starts to make sense.

In this article, we’ll understand recursion using a simple factorial example, and visualize it with a recursion tree and the call-back flow.

🔁 What is Recursion?

Recursion is when a function calls itself to solve a smaller part of the problem. But to avoid infinite loops, every recursive function must have a base case—a condition to stop recursion.

✨ Factorial Using Recursion in Python

Let’s take the classic example: factorial.

Factorial of n (written as n!) is the product of all positive integers from 1 to n. For example, 5! = 5 × 4 × 3 × 2 × 1 = 120

Here’s the recursive code for factorial:

def factorial_recursive(n):
    if n == 0 or n == 1:
        return 1
    return n * factorial_recursive(n - 1)

# Example usage
print(factorial_recursive(5))  # Output: 120
        

🌳 Recursion Tree for factorial_recursive(5)

To understand how this works, let’s draw the recursive calls as a tree structure:

factorial_recursive(5)
→ 5 * factorial_recursive(4)
             ↓
       4 * factorial_recursive(3)
                   ↓
             3 * factorial_recursive(2)
                         ↓
                   2 * factorial_recursive(1)
                               ↓
                         return 1   ← base case
        

Each function pauses and waits for the result of the next one.

🪜 Call Stack and Return Flow

Now, let’s see how the function returns back up with values:

factorial_recursive(1) → returns 1
factorial_recursive(2) → 2 * 1 = 2
factorial_recursive(3) → 3 * 2 = 6
factorial_recursive(4) → 4 * 6 = 24
factorial_recursive(5) → 5 * 24 = 120
        

Each function call resumes with the value returned from the one it called.

🔁 Final Execution Flow

Here’s how the entire call looks in a single flow:

factorial_recursive(5)
= 5 * factorial_recursive(4)
= 5 * (4 * factorial_recursive(3))
= 5 * (4 * (3 * factorial_recursive(2)))
= 5 * (4 * (3 * (2 * factorial_recursive(1))))
= 5 * (4 * (3 * (2 * 1)))
= 5 * 4 * 3 * 2 * 1
= 120
        

📌 Key Concepts to Remember

• Recursive Case: This is where the function calls itself with a smaller input.
• Base Case: The condition where recursion stops. In our case, when n == 0 or n == 1.
• Call Stack: Each recursive call is placed on the stack until the base case is reached, then the stack "unwinds" as each call returns its result.

🧠 Why Use Recursion?

Recursion is very useful when:

• The problem is naturally recursive (e.g., tree traversal, factorial, Fibonacci, etc.)
• You want simpler and cleaner code (though iterative solutions may be faster in some cases)

🧪 Bonus: Try it Yourself!

Change the function to print something in each step:

def factorial_trace(n):
    print(f"Calling factorial({n})")
    if n == 0 or n == 1:
        print(f"Returning 1 from factorial({n})")
        return 1
    result = n * factorial_trace(n - 1)
    print(f"Returning {result} from factorial({n})")
    return result

factorial_trace(5)
        

This will let you see the recursive flow in real time!