Recursive Functions

Introduction

Recursion is one of the most powerful and beautiful concepts in computer science. A recursive function is a function that calls itself to break a problem into smaller, simpler sub-problems until it reaches a point that can be solved directly.

Many problems in mathematics and computer science are naturally recursive: computing factorials, Fibonacci numbers, traversing tree structures, and solving puzzles like the Tower of Hanoi.

While recursion can produce elegant and clean code, it must be used carefully. Without a proper base case, a recursive function will call itself infinitely and crash.

University Definition

Recursion is a programming technique where a function calls itself directly or indirectly to solve a problem by breaking it into smaller instances of the same problem. Every recursive function must have a base case that terminates the recursion and a recursive case that reduces the problem toward the base case.

Anatomy of a Recursive Function

Every recursive function has two essential parts:

Base Case

The condition that stops the recursion. Without it, the function calls itself forever. It is the "exit door" of the recursion.

Recursive Case

The part where the function calls itself with a modified (usually smaller) argument, moving toward the base case.

Example — Factorial Using Recursion

The factorial of a number n (written as n!) is the product of all positive integers from 1 to n. By definition, 0! = 1.

def factorial(n):
    # Base case
    if n == 0 or n == 1:
        return 1
    # Recursive case
    else:
        return n * factorial(n - 1)

print(factorial(5))
print(factorial(0))
print(factorial(10))

Output:
120
1
3628800

How it works for factorial(5):

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

How Recursion Works — The Call Stack

Each recursive call adds a new stack frame to the call stack. When the base case is reached, the stack begins to "unwind"—each frame returns its result to the previous one.

Call Stack for factorial(4):

  factorial(4)   ← pushed (waiting for factorial(3))
    factorial(3) ← pushed (waiting for factorial(2))
      factorial(2) ← pushed (waiting for factorial(1))
        factorial(1) ← pushed (returns 1, base case!)

  Unwinding:
        factorial(2) = 2 * 1 = 2  ← popped
      factorial(3) = 3 * 2 = 6    ← popped
    factorial(4) = 4 * 6 = 24      ← popped

Example — Countdown

def countdown(n):
    if n <= 0:
        print("Liftoff!")
        return
    print(n)
    countdown(n - 1)

countdown(5)

Output:
5
4
3
2
1
Liftoff!

Example — Sum of Natural Numbers

def sum_n(n):
    if n == 1:
        return 1
    return n + sum_n(n - 1)

print("Sum of 1 to 10 =", sum_n(10))
print("Sum of 1 to 5 =", sum_n(5))

Output:
Sum of 1 to 10 = 55
Sum of 1 to 5 = 15

Recursion vs Iteration

Recursion

Function calls itself.
Uses the call stack (uses more memory).
Code is often cleaner and more elegant.
Best for problems with natural recursive structure (trees, divide-and-conquer).
Risk of stack overflow for deep recursion.

Iteration (Loops)

Uses loops (for/while).
Uses constant memory (no stack frames).
Code can be more verbose.
Best for simple repetitive tasks.
No risk of stack overflow.

Factorial — Both Approaches

# Recursive
def factorial_recursive(n):
    if n <= 1:
        return 1
    return n * factorial_recursive(n - 1)

# Iterative
def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

print("Recursive:", factorial_recursive(5))
print("Iterative:", factorial_iterative(5))

Output:
Recursive: 120
Iterative: 120

Real-Life Analogy

Imagine you are standing in a line at a ticket counter and you ask the person in front of you, "What position am I in?" That person does not know either, so they ask the person in front of them. This keeps going until someone at the front says, "I am position 1." Then each person adds 1 and passes the answer back. Eventually, you learn your position. This chain of questions is like recursion—each person calls the same "function" (asking the person ahead) until a base case (the front of the line) is reached.

Advantages and Disadvantages of Recursion

Advantages

Makes code shorter and cleaner.
Ideal for problems with recursive structure.
Simplifies complex problems like tree traversal.
Used in divide-and-conquer algorithms (merge sort, quicksort).

Disadvantages

Uses more memory (call stack).
Can cause stack overflow for deep recursion.
Slower than iteration due to function call overhead.
Harder to debug for beginners.

Key Points

A recursive function calls itself.

Every recursive function needs a base case to stop.

The recursive case must move toward the base case.

Each call adds a frame to the call stack.

Recursion can be replaced by iteration in most cases.

Python has a default recursion limit of 1000 calls.

University Exam Tip

Common exam questions:

Define recursion. What are its two essential components?
Write a recursive function to find the factorial of a number.
Differentiate between recursion and iteration.
What is the base case and why is it important?
Trace the recursive calls for factorial(4).

Practice Questions

Q1. What is recursion?

Answer: Recursion is a technique where a function calls itself to solve a problem by breaking it into smaller sub-problems.

Q2. What happens if you forget the base case?

Answer: The function calls itself infinitely until Python raises a RecursionError (maximum recursion depth exceeded).

Q3. Trace the recursion for factorial(3).

factorial(3)
= 3 * factorial(2)
= 3 * 2 * factorial(1)
= 3 * 2 * 1
= 6

Q4. Write a recursive function to compute the power of a number: power(base, exp).

def power(base, exp):
    if exp == 0:
        return 1
    return base * power(base, exp - 1)

print(power(2, 10))  # 1024
print(power(3, 4))   # 81

Q5. When should you prefer iteration over recursion?

Answer: When performance and memory efficiency matter, or when the recursion depth might be very large. Iteration uses constant memory while recursion uses stack memory for each call.