What is Recursion?

Recursion is when a function calls itself to solve a problem by breaking it into smaller, identical sub-problems. Every recursive function needs two parts: a base case (stopping condition) and a recursive case (the self-call).

def countdown(n):
    """Print countdown from n to 1."""
    if n <= 0:        # BASE CASE: stop recursion
        print("Go!")
        return
    print(n)
    countdown(n - 1)  # RECURSIVE CASE: call with smaller n

countdown(5)
# 5, 4, 3, 2, 1, Go!

Without a base case, the function would call itself forever, causing a RecursionError (stack overflow).

Classic Examples: Factorial and Fibonacci

Factorial (n!) = n * (n-1) * ... * 1. The base case is 0! = 1. Fibonacci is defined as F(n) = F(n-1) + F(n-2) with base cases F(0) = 0, F(1) = 1.

def factorial(n):
    """Calculate n! recursively."""
    if n <= 1:          # base case
        return 1
    return n * factorial(n - 1)  # recursive case

print(factorial(5))  # 120 (5 * 4 * 3 * 2 * 1)

def fibonacci(n):
    """Calculate nth Fibonacci number."""
    if n <= 0:
        return 0        # base case 1
    if n == 1:
        return 1        # base case 2
    return fibonacci(n - 1) + fibonacci(n - 2)

print([fibonacci(i) for i in range(10)])
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Warning: Naive Fibonacci is O(2^n) because it recalculates the same values repeatedly. Use memoisation to fix this.

Memoisation and Avoiding Stack Overflow

Memoisation caches previously computed results, turning O(2^n) Fibonacci into O(n). Python provides functools.lru_cache for easy memoisation.

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n):
    """Memoised Fibonacci - O(n) instead of O(2^n)."""
    if n <= 0:
        return 0
    if n == 1:
        return 1
    return fib_memo(n - 1) + fib_memo(n - 2)

print(fib_memo(50))  # 12586269025 (instant, not years!)

# Python's recursion limit (default ~1000)
import sys
print(sys.getrecursionlimit())  # 1000

# For very deep recursion, convert to iteration:
def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

Python has a default recursion limit of ~1000 calls. For deeper recursion, consider converting to an iterative approach.

Key Vocabulary

Base Case

The stopping condition that prevents infinite recursion. Without it, the function never stops calling itself.

Recursive Case

The part of the function that calls itself with a smaller or simpler input, moving toward the base case.

Call Stack

A stack of function calls maintained by Python. Each recursive call adds a frame; too many causes a stack overflow.

Memoisation

Caching return values of previous function calls to avoid redundant computation in recursive algorithms.

Worked Examples

1

Trace factorial(4) through the call stack

# Call stack trace for factorial(4):
# factorial(4) -> 4 * factorial(3)
#   factorial(3) -> 3 * factorial(2)
#     factorial(2) -> 2 * factorial(1)
#       factorial(1) -> 1  (BASE CASE)
#     factorial(2) -> 2 * 1 = 2
#   factorial(3) -> 3 * 2 = 6
# factorial(4) -> 4 * 6 = 24

# The stack "unwinds" as each call returns its result

Key insight: Each call waits for the inner call to finish, then multiplies the result. The base case triggers the unwinding.

2

Recursively sum a list of numbers

def recursive_sum(numbers):
    """Sum a list using recursion."""
    if not numbers:      # base case: empty list
        return 0
    return numbers[0] + recursive_sum(numbers[1:])

print(recursive_sum([3, 7, 1, 9]))  # 20
# 3 + recursive_sum([7, 1, 9])
# 3 + 7 + recursive_sum([1, 9])
# 3 + 7 + 1 + recursive_sum([9])
# 3 + 7 + 1 + 9 + recursive_sum([])
# 3 + 7 + 1 + 9 + 0 = 20

Pattern: Process the first element, then recurse on the rest. This works for any list operation.

3

Recursive binary search

def binary_search_recursive(data, target, low=0, high=None):
    """Recursive binary search."""
    if high is None:
        high = len(data) - 1

    if low > high:         # base case: not found
        return -1

    mid = (low + high) // 2
    if data[mid] == target:    # base case: found
        return mid
    elif data[mid] < target:
        return binary_search_recursive(data, target, mid + 1, high)
    else:
        return binary_search_recursive(data, target, low, mid - 1)

nums = [2, 5, 8, 12, 16, 23, 38, 56]
print(binary_search_recursive(nums, 23))  # 5

Two base cases: element found (return index) or search space exhausted (return -1). The recursive calls narrow the search range.

Knowledge Check

Select the correct answer for each question. Click "Check Answer" to see if you are right.

Question 1

What happens if a recursive function has no base case?

It returns None It calls itself forever until a RecursionError (stack overflow) It runs once and stops Python automatically adds a base case

Question 2

What is the value of factorial(0)?

0 Error 1 None

Question 3

Why is naive recursive Fibonacci inefficient for large n?

It uses too much memory for the base cases The base cases are incorrect Python cannot handle large integers It recalculates the same values many times (exponential redundancy)

Question 4

What does @lru_cache do to a recursive function?

Caches return values so repeated calls with the same arguments return instantly Converts it to an iterative function Removes the recursion limit Makes the function run in parallel

Question 5

What is the default recursion limit in Python?

100 1,000 10,000 Unlimited

Python Recursion