Advertisement
⚙️ Functions

Python Recursion – Functions that Call Themselves

Recursion is a technique where a function calls itself to solve a problem. It works by breaking a large problem into smaller, identical sub-problems. Every recursive solution has two parts: a base case (where it stops) and a recursive case (where it calls itself).

⏱️ 22 min read 🎯 Intermediate 📅 Updated 2026

How Recursion Works

When a function calls itself, a new frame is added to the call stack. When the base case is reached, the frames unwind and return values back up the chain.

Python
def countdown(n):
    if n <= 0:           # Base case - MUST exist to prevent infinite loop
        print("Done!")
        return
    print(n)
    countdown(n - 1)    # Recursive case - calls itself with smaller n

countdown(5)
▶ Output
5 4 3 2 1 Done!

Classic Example – Factorial

n! (n factorial) = n × (n-1) × (n-2) × ... × 1. This is the quintessential recursion example.

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

print(factorial(5))   # 120  (5×4×3×2×1)
print(factorial(10))  # 3628800
▶ Output
120 3628800
Advertisement

Fibonacci Sequence

Fibonacci: each number is the sum of the two preceding ones. 0, 1, 1, 2, 3, 5, 8, 13...

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

for i in range(8):
    print(fibonacci(i), end=" ")
▶ Output
0 1 1 2 3 5 8 13
💡
Tip

Naive Fibonacci recursion is exponentially slow (O(2^n)). Use memoization (@functools.lru_cache) for performance.

Recursion vs Iteration

Recursion is elegant but not always the best choice. Python has a default recursion limit of 1000 calls (sys.setrecursionlimit()).

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

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

print(factorial_recursive(10))  # 3628800
print(factorial_iterative(10))  # 3628800 - same result
▶ Output
3628800 3628800

Base Case, the Call Stack, and Why Recursion Blows Up

Every recursive function needs two parts: a base case that stops the recursion, and a recursive case that moves toward it. Forget the base case and Python raises RecursionError: maximum recursion depth exceeded — because each call adds a frame to the call stack, and Python caps that at about 1000 frames by default.

import sys
print(sys.getrecursionlimit())   # 1000

def countdown(n):
    if n == 0:          # base case — without this it never stops
        return
    print(n)
    countdown(n - 1)    # recursive case moves toward base

Naive recursion can be exponentially slow

Plain recursive Fibonacci recomputes the same values over and over — fib(35) makes ~30 million calls. Cache results with lru_cache and it drops to linear:

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    return n if n < 2 else fib(n-1) + fib(n-2)

Rule of thumb: reach for recursion when the data is itself nested (trees, JSON, folders). For flat counting loops, an iterative for is faster and can't overflow the stack.

🏋️ Practical Exercise

Write recursive functions:

  1. Implement factorial(n) recursively with a proper base case.
  2. Implement fibonacci(n) recursively and print the first 10 numbers.
  3. Write a recursive function that sums a list of numbers.
  4. Write a recursive countdown that prints from n to 0.

🔥 Challenge Exercise

Write a recursive function that walks a nested list (a list that may contain other lists) and returns the flat sum of all numbers inside it, at any depth. Then compare the recursive Fibonacci with an iterative version and time both for n = 30 to see why naive recursion is slow. Bonus: speed up the recursive version with functools.lru_cache.

📋 Summary

  • Recursion is when a function calls itself to solve a smaller version of a problem.
  • Every recursive function needs a base case (to stop) and a recursive case (to progress toward it).
  • Without a reachable base case, recursion runs forever and raises RecursionError.
  • Recursion can be elegant for tree-like and divide-and-conquer problems, but iteration is often faster and uses less memory.
  • Python’s default recursion depth is about 1000; change it with sys.setrecursionlimit() cautiously.
  • Memoization (e.g. functools.lru_cache) avoids recomputing overlapping subproblems.

Interview Questions on Recursion

  • What is recursion?
  • What are the two essential parts of every recursive function?
  • What is a base case and why is it required?
  • What is the difference between recursion and iteration?
  • What is a stack overflow / RecursionError and what causes it?
  • What is Python’s default recursion limit and how do you change it?
  • How can memoization improve recursive performance?
⚙️ Function Basics ↩️ Return Values 🔁 For Loops 🔁 Generators 📚 Lists

FAQ

When should I use recursion instead of a loop? +

Recursion shines for naturally recursive structures — trees, nested data, divide-and-conquer algorithms like quicksort. For simple repetition, a loop is usually clearer and more efficient because it avoids call-stack overhead.

What causes a RecursionError? +

It happens when recursion goes too deep — typically because the base case is missing or never reached, so the call stack exceeds Python’s limit (about 1000 frames by default).

Why is recursive Fibonacci so slow? +

The naive version recomputes the same subproblems exponentially many times. Memoizing results with functools.lru_cache, or switching to an iterative approach, reduces it to linear time.

Does Python optimize tail recursion? +

No. Unlike some languages, CPython does not perform tail-call optimization, so deep tail-recursive functions still grow the stack. Prefer iteration when recursion depth could be large.

Advertisement