DSA Recursion

Recursion is a programming technique where a function solves a problem by calling itself. Instead of solving the entire problem at once, a recursive function breaks the problem into smaller, simpler versions of the same problem and calls itself on each smaller version until it reaches a case simple enough to solve directly.

Recursion is one of the most important concepts in DSA. Many data structures (trees, graphs) and algorithms (merge sort, quicksort, DFS) are naturally expressed using recursion.

The Two Essential Parts of Recursion

Every recursive function must have two components. Without both, the function either gives wrong results or runs forever.

1. Base Case

The condition where the function stops calling itself. It is the simplest version of the problem that can be solved directly. Without a base case, recursion would continue infinitely, causing a stack overflow.

2. Recursive Case

The part where the function calls itself with a smaller or simpler input, moving step by step toward the base case.

A Simple First Example: Countdown


def countdown(n):
    if n == 0:           # Base case — stop here
        print("Done!")
        return
    print(n)
    countdown(n - 1)     # Recursive case — smaller input

countdown(5)
# Output:
# 5
# 4
# 3
# 2
# 1
# Done!

Each call to countdown prints one number and then calls itself with n - 1. When n reaches 0, the base case triggers and the recursion ends.

How Recursion Uses the Call Stack

Each time a function calls itself, a new stack frame is added to the call stack. Each frame holds the local variables for that call. When the base case is reached, the frames are resolved in reverse order (LIFO), and the results bubble back up.


# Call stack visualization for factorial(3)
# factorial(3) waits for factorial(2)
#   factorial(2) waits for factorial(1)
#     factorial(1) returns 1  <-- base case
#   factorial(2) returns 2 * 1 = 2
# factorial(3) returns 3 * 2 = 6

Classic Recursive Problems

1. Factorial

The factorial of a number n (written as n!) is the product of all positive integers from 1 to n. Example: 5! = 5 × 4 × 3 × 2 × 1 = 120.


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

print(factorial(5))   # Output: 120
print(factorial(6))   # Output: 720

2. Fibonacci Sequence

Each Fibonacci number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13 ...


def fibonacci(n):
    if n <= 1:              # Base case
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)   # Recursive case

print(fibonacci(7))   # Output: 13

Note: This naive version has O(2ⁿ) time complexity because it recalculates the same values many times. This will be optimized with memoization in the Dynamic Programming topic.

3. Sum of a List


def sum_list(lst):
    if len(lst) == 0:          # Base case — empty list
        return 0
    return lst[0] + sum_list(lst[1:])   # First element + sum of rest

print(sum_list([1, 2, 3, 4, 5]))   # Output: 15

4. Power of a Number


def power(base, exp):
    if exp == 0:               # Base case — anything to the power 0 is 1
        return 1
    return base * power(base, exp - 1)

print(power(2, 10))   # Output: 1024

5. Reversing a String


def reverse_string(s):
    if len(s) == 0:            # Base case
        return ""
    return reverse_string(s[1:]) + s[0]   # Recursive case

print(reverse_string("hello"))   # Output: olleh

Recursion vs Iteration

Most recursive problems can also be solved iteratively (using loops). The choice depends on clarity and context.

Factorial — Iterative Version


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

print(factorial_iterative(5))   # Output: 120

Both versions produce the same result. The recursive version is often more elegant for problems that are naturally recursive (like tree traversal). The iterative version avoids call stack overhead and is typically more memory-efficient.

Common Pitfalls in Recursion

Missing Base Case — Infinite Recursion


# WARNING: This will cause a RecursionError (stack overflow)
def broken(n):
    print(n)
    broken(n - 1)   # No base case — never stops!

Python's Recursion Limit

Python has a default recursion limit of 1000. For problems that require deeper recursion, the limit can be adjusted or an iterative approach should be used.


import sys
sys.setrecursionlimit(5000)   # Increase recursion limit (use with caution)

Tail Recursion

A recursive call is tail recursive if the recursive call is the very last operation in the function. Python does not optimize tail recursion, but understanding the concept is useful when working in other languages.


# Tail recursive factorial with accumulator
def factorial_tail(n, accumulator=1):
    if n == 0:
        return accumulator
    return factorial_tail(n - 1, n * accumulator)   # Tail position

print(factorial_tail(5))   # Output: 120

Key Points

  • Recursion is when a function calls itself to solve a smaller version of the same problem.
  • Every recursive function must have a base case (stop condition) and a recursive case (smaller input).
  • Recursion uses the call stack — deep recursion can cause stack overflow if the base case is never reached.
  • Classic recursive problems include factorial, Fibonacci, list sum, and string reversal.
  • Recursive solutions are often more readable for naturally hierarchical problems like trees.
  • Naive recursion can be slow (O(2ⁿ) for Fibonacci). Memoization and dynamic programming fix this — covered in later topics.
Previous lessons
Back to courses
Next lessons

Leave a Comment