Recursion in Python: Concept, Examples, and Common Pitfalls

A recursive function is one that calls itself, reducing the problem size on each call until a base case stops the chain.

That single sentence is the entire concept. Everything else in this article is mechanics: how to write the base case, what the call stack looks like, where Python draws the line on depth, and how memoisation rescues performance. If you are working through Python example programs for CRT or placement prep, recursion appears in roughly one out of every five problem sets across portals used by Tier-2 and Tier-3 colleges.

How Recursion Works: Base Case and Recursive Case

Every recursive function has exactly two structural parts:

• Base case — a condition that returns a value directly, without calling the function again.
• Recursive case — the branch that calls the function with a smaller or simpler argument.

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

countdown(3)

• Output:
  • 3
  • 2
  • 1
  • Done

Remove the if n == 0 check and the function calls itself forever (in theory). In practice, Python halts it after 1000 frames with a RecursionError. More on that limit below.

Why the base case must come first

Put the recursive call before the base-case check and the function never gets a chance to stop. This is the single most common bug in student submissions: the base case exists, but a recursive call above it fires first.

Classic Recursive Examples

Factorial

n! = n multiplied by every positive integer below it. 0! = 1 by definition.

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

print(factorial(5))

• Output: 120
• Verification: 5 x 4 x 3 x 2 x 1 = 120

Sum of First n Integers

The iterative version of this appears in the sum of array elements article. Here is the recursive counterpart:

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

print(sum_n(5))

• Output: 15
• Verification: 5 + 4 + 3 + 2 + 1 = 15

Fibonacci Sequence

Each term is the sum of the two preceding terms: 0, 1, 1, 2, 3, 5, 8, 13 …

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

print(fib(6))

• Output: 8
• Verification: fib(0)=0, fib(1)=1, fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5, fib(6)=8

This naive version has exponential time complexity. For fib(30) the interpreter makes over 2.6 million calls. The memoisation section below fixes this.

Recursive List Traversal

Recursion can process a list element by element, peeling off the head on each call:

def print_list(lst):
    if not lst:
        return
    print(lst[0])
    print_list(lst[1:])

print_list(["a", "b", "c"])

• Output:
  • a
  • b
  • c

This pattern generalises to tree traversal. A binary tree node has a value plus two sub-trees (left, right). Visiting every node is the same structure: process current node, recurse left, recurse right. CRT questions on tree traversal use this exact pattern with a node class instead of a list.

Digit Decomposition (Armstrong Number Variant)

Breaking a number into its digits is another natural recursion. The Armstrong number check uses this idea to test whether the sum of cubed digits equals the original number. Here is the recursive digit-sum:

def digit_sum(n):
    if n == 0:
        return 0
    return (n % 10) + digit_sum(n // 10)

print(digit_sum(1234))

• Output: 10
• Verification: 1 + 2 + 3 + 4 = 10

The Call Stack: What Happens Under the Hood

Each recursive call creates a new frame on the call stack. The frame stores the function’s local variables and the return address. When the base case returns, frames pop off one by one, each completing its suspended multiplication (or addition, or whatever operation wraps the recursive call).

Here is what happens for factorial(4):

Step	Call	Stack depth	Returns
1	factorial(4)	1	waiting
2	factorial(3)	2	waiting
3	factorial(2)	3	waiting
4	factorial(1)	4	waiting
5	factorial(0)	5	1
6	back to factorial(1)	4	1 x 1 = 1
7	back to factorial(2)	3	2 x 1 = 2
8	back to factorial(3)	2	3 x 2 = 6
9	back to factorial(4)	1	4 x 6 = 24

Five frames at peak. For factorial(1000) the stack would need 1001 frames, which is just past the default limit.

Memory cost

Each frame costs a fixed amount of memory (roughly 400 to 900 bytes in CPython 3.12, depending on the number of local variables). Deep recursion can therefore consume megabytes of stack space even when the function’s logic is trivial.

Recursion Depth Limit and sys.setrecursionlimit

Python caps recursion depth to prevent an out-of-control function from crashing the process with a segfault. The default is 1000.

import sys
print(sys.getrecursionlimit())  # 1000 on most installations

You can raise the ceiling:

sys.setrecursionlimit(5000)

But raising the limit is a band-aid, not a fix. If the algorithm genuinely needs thousands of recursive calls, convert it to an iterative version with an explicit stack (a Python list used as a LIFO). The Python documentation for sys.getrecursionlimit() notes that the highest safe value depends on the platform’s C stack size, which varies across operating systems.

Common pitfall: RecursionError in production

def broken(n):
    # Missing base case
    return broken(n - 1)

broken(5)

• Output: RecursionError: maximum recursion depth exceeded

The fix is always structural: add or correct the base case. Never “fix” a RecursionError by raising the limit unless you have confirmed the recursion depth is bounded and the OS stack can handle it.

Tail recursion: why Python ignores it

In languages like Scheme or Haskell, a function whose recursive call is the very last operation (tail position) can reuse the current frame instead of pushing a new one. CPython deliberately does not do this. Guido van Rossum’s rationale: tail-call optimisation destroys stack traces, making debugging harder. The practical consequence is simple: if your recursion goes deep, rewrite as a loop.

# Tail-recursive style (Python does NOT optimise this)
def factorial_tail(n, acc=1):
    if n == 0:
        return acc
    return factorial_tail(n - 1, acc * n)

This still pushes one frame per call in CPython. It reads nicely but performs identically to the non-tail version.

Memoisation with @functools.cache

Naive Fibonacci calls fib(n-1) and fib(n-2), which means overlapping sub-problems balloon exponentially. @functools.cache (available since Python 3.9) stores each result after the first computation and returns it instantly on repeat calls. The Python documentation for functools.cache describes it as an unbounded LRU cache.

import functools

@functools.cache
def fib_memo(n):
    if n <= 1:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

print(fib_memo(30))

• Output: 832040
• Verification: the 30th Fibonacci number (0-indexed) is 832040

Without the decorator, fib(30) generates over 2.6 million calls. With @functools.cache, it makes exactly 31 calls (one per unique input from 0 to 30). Time complexity drops from O(2^n) to O(n).

When memoisation is not enough

Memoisation eliminates redundant computation but does not eliminate stack depth. fib_memo(1000) still needs 1000 frames on the first call (before caching fills up). For very large n, an iterative bottom-up approach is safer:

def fib_iter(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(fib_iter(1000))  # works instantly, no stack risk

Use recursion plus memoisation for clarity on moderate inputs. Use iteration for inputs that approach or exceed the recursion limit.

Choosing Between Recursion and Iteration

Factor	Recursion	Iteration
Readability for tree/graph problems	Cleaner	Requires explicit stack
Stack memory	O(n) frames	O(1) extra space (for simple loops)
Python depth limit	1000 default	No limit
Debugging	Stack trace shows each frame	Single loop frame
Performance (CPython)	Slower per call (frame allocation overhead)	Faster for simple accumulation

The rule of thumb: prefer recursion when the problem is naturally recursive (trees, divide-and-conquer, backtracking) and the input size stays under a few hundred. Prefer iteration when the recursion depth is proportional to input size and inputs can grow large.

Recursive Thinking in AI and Beyond

Tree traversal, backtracking search, and divide-and-conquer algorithms all rely on recursive decomposition. If you have built the examples above from scratch, you already understand the control-flow pattern that powers depth-first search in graph problems and recursive prompt-chain evaluation in LLM agent systems.

• TinkerLLM (₹299) lets you build and run recursive agent loops on real LLM APIs, where one function call triggers another based on intermediate output, the same base-case-then-recurse structure you practised here applied to prompt chains instead of integers.