Chapter 34 of 54

Recursion in Python

Have you ever stood between two mirrors and seen your reflection repeat again and again? Or opened a set of Russian dolls, where each doll contains a smaller doll, until you reach the tiniest one?

That idea, something defined in terms of a smaller version of itself, is called recursion. In programming, it means a function that calls itself.

Recursion is a key idea for Data Structures and Algorithms (trees, backtracking, divide and conquer), so it's worth understanding well.

What is Recursion?

Recursion is a technique where a function solves a problem by calling itself on a smaller version of the same problem.

A function that calls itself is called a recursive function.

Every correct recursive function has two parts:

Part

What it does

Base case

The simplest version of the problem, answered directly without calling the function again. This is where recursion stops.

Recursive case

The function calls itself with a smaller input, moving closer to the base case.


A First Example: Countdown

def countdown(n):
    if n == 0:              # base case
        print("Liftoff!")
        return
    print(n)
    countdown(n - 1)        # recursive case

countdown(3)

Output:

3
2
1
Liftoff!

Each call prints a number and then calls countdown with a number one smaller. When n reaches 0, the base case stops the chain.

Of course, a simple while loop could do this too. Recursion becomes really useful when a problem naturally breaks into smaller copies of itself.


Factorial: The Classic Example

The factorial of n (written n!) is the product of all numbers from 1 to n:

5! = 5 × 4 × 3 × 2 × 1 = 120

Notice that 5! = 5 × 4!, and 4! = 4 × 3!, and so on. The problem contains a smaller copy of itself:

n! = n × (n - 1)!     for n > 1
1! = 1                (and 0! = 1)

That translates directly into code:

def factorial(n):
    if n <= 1:                      # base case
        return 1
    return n * factorial(n - 1)     # recursive case

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

Output:

120
1
3628800

How Recursion Works: The Call Stack

Every time a function is called, Python creates a frame that stores that call's local variables. Frames are kept on the call stack. A new call is pushed on top; when a call returns, its frame is removed.

Here's what happens for factorial(4):

Going down (calls are pushed):

factorial(4) = 4 * factorial(3)
                   factorial(3) = 3 * factorial(2)
                                      factorial(2) = 2 * factorial(1)
                                                         factorial(1) = 1   <-- base case

Coming back up (results are returned):

                                                         factorial(1) returns 1
                                      factorial(2) returns 2 * 1 = 2
                   factorial(3) returns 3 * 2 = 6
factorial(4) returns 4 * 6 = 24

Each call waits for the call below it to finish, then uses its result. You can see this order by adding some prints:

def factorial(n):
    print(f"Calling factorial({n})")
    if n <= 1:
        return 1
    result = n * factorial(n - 1)
    print(f"factorial({n}) returns {result}")
    return result

factorial(3)

Output:

Calling factorial(3)
Calling factorial(2)
Calling factorial(1)
factorial(2) returns 2
factorial(3) returns 6

Complexity

factorial(n) makes n calls, each doing a constant amount of work, so its time complexity is O(n). Because up to n frames sit on the stack at once, it also uses O(n) extra space. An iterative loop would use only O(1) space.


More Recursive Examples

Sum of Digits

The sum of digits of 1234 is 4 + (sum of digits of 123):

def sum_of_digits(n):
    if n < 10:                          # a single digit
        return n
    return n % 10 + sum_of_digits(n // 10)

print(sum_of_digits(1234))
print(sum_of_digits(9075))

Output:

10
21

Power (an)

def power(a, n):
    if n == 0:
        return 1
    return a * power(a, n - 1)

print(power(2, 10))
print(power(3, 4))

Output:

1024
81

Reversing a String

The reverse of a string is (reverse of everything after the first character) followed by the first character:

def reverse(text):
    if len(text) <= 1:
        return text
    return reverse(text[1:]) + text[0]

print(reverse("python"))

Output:

nohtyp

Palindrome Check

A string is a palindrome if its first and last characters match and the middle part is also a palindrome:

def is_palindrome(text):
    if len(text) <= 1:
        return True
    if text[0] != text[-1]:
        return False
    return is_palindrome(text[1:-1])

print(is_palindrome("madam"))
print(is_palindrome("racecar"))
print(is_palindrome("python"))

Output:

True
True
False

Fibonacci and the Cost of Repeated Work

In the Fibonacci sequence, each number is the sum of the two before it:

0, 1, 1, 2, 3, 5, 8, 13, 21, ...
fib(0) = 0, fib(1) = 1, fib(n) = fib(n-1) + fib(n-2)

This function makes two recursive calls:

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

for i in range(10):
    print(fib(i), end=" ")

Output:

0 1 1 2 3 5 8 13 21 34

It looks elegant, but it is very slow for larger n. Look at the calls made for fib(4):

                fib(4)
              /        \
         fib(3)         fib(2)
        /      \        /    \
    fib(2)   fib(1)  fib(1) fib(0)
    /    \
fib(1) fib(0)

fib(2) is calculated twice. For bigger inputs, the same values are recalculated again and again, and the number of calls grows exponentially (roughly O(2n) time; the stack depth is only O(n)). Let's count:

calls = 0

def fib(n):
    global calls
    calls += 1
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(30))
print("Calls made:", calls)

Output:

832040
Calls made: 2692537

Over 26 lakh calls to compute one number!

Fixing It with Memoization

Memoization means remembering results that were already calculated. Python's functools module provides cache (available since Python 3.9) to do this automatically:

from functools import cache

@cache
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(30))
print(fib(100))

Output:

832040
354224848179261915075

The @cache line is a decorator (covered in the Decorators chapter). It stores each result, so every fib(k) is calculated only once. The time complexity drops from exponential to O(n). This idea is the foundation of Dynamic Programming.


Recursion Limit and RecursionError

Each call adds a frame to the stack, and the stack isn't infinite. Python sets a limit on how deep recursion can go:

import sys
print(sys.getrecursionlimit())

Output:

1000

If you forget the base case, the function keeps calling itself until it hits this limit:

def countdown(n):
    print(n)
    countdown(n - 1)    # no base case!

countdown(3)

This prints numbers for a while and then stops with:

RecursionError: maximum recursion depth exceeded

You can raise the limit with sys.setrecursionlimit(), but that's usually a sign you should use a loop instead. Unlike some languages, Python does not perform tail-call optimisation, so deep recursion always uses stack space.


Common Mistakes

  • Missing base case: the function never stops and raises RecursionError.

  • Not moving towards the base case: for example, calling factorial(n) instead of factorial(n - 1).

  • Forgetting to return the recursive call: writing n * factorial(n - 1) without return makes the function return None.

  • Wrong base case for some inputs: if n == 1 fails for factorial(0): n goes 0, -1, -2, ... and never reaches 1, so it ends in a RecursionError. if n <= 1 is safer.


Recursion vs Iteration

Recursion

Iteration (loops)

Function calls itself

Repeats using for / while

Stops at the base case

Stops when the loop condition is false

Uses stack space for every call

Usually uses constant extra space

Can hit RecursionError for deep inputs

No depth limit

Natural for trees, backtracking, divide and conquer

Natural for simple repetition and counting

Any recursive solution can be rewritten with loops (sometimes with an explicit stack). Choose whichever is clearer for the problem.


Summary

  • A recursive function calls itself on a smaller version of the problem.

  • It always needs a base case (where it stops) and a recursive case (that moves towards the base case).

  • Python tracks calls on the call stack; the default recursion limit is 1000.

  • Recursion uses O(depth) extra space for stack frames.

  • Repeated sub-problems (like naive Fibonacci) can be fixed with memoization.

Practice Problems

  1. Print the numbers from 1 to n using recursion (no loops).

  2. Count the number of digits in a positive integer.

  3. Find the GCD of two numbers using Euclid's rule: gcd(a, b) = gcd(b, a % b), with gcd(a, 0) = a.

  4. Count how many times a character appears in a string.

  5. Convert a decimal number to its binary string (for example, 10 becomes "1010").

Trust the recursion: assume the smaller call already works, and focus on how to use its answer plus a correct base case.