Recursion Explained with Real Examples 2026

Recursion is a technique where a function calls itself to solve a smaller version of the same problem. It feels magical the first time it clicks and impossible before that. This 2026 guide walks you through recursion using Python examples that show the technique in action: factorial, Fibonacci, tree traversal, and directory listing. You will learn to identify recursion candidates, write the base case correctly, and avoid the two mistakes that crash every beginner’s code (missing base case + inefficient overlapping subproblems).

What recursion actually is

A recursive function calls itself with a smaller input until it reaches a case simple enough to solve directly. Think of Russian nesting dolls: opening each one reveals a smaller version until you reach the tiny one at the center. That tiny one is your base case.

The mental shift beginners have to make: instead of thinking “how do I solve this problem step by step”, think “if I already had the solution for a smaller version, how would I use it to solve the bigger version”. That reframe is 80 percent of understanding recursion.

Example 1: Factorial (the classic starter)

def factorial(n):
    if n <= 1:              # BASE CASE: factorial(0) = factorial(1) = 1
        return 1
    return n * factorial(n - 1)   # RECURSIVE CASE

print(factorial(5))         # 120

Trace what happens when you call factorial(5):

• factorial(5) needs 5 * factorial(4)
• factorial(4) needs 4 * factorial(3)
• factorial(3) needs 3 * factorial(2)
• factorial(2) needs 2 * factorial(1)
• factorial(1) hits the base case, returns 1
• The chain unwinds: 2*1=2, 3*2=6, 4*6=24, 5*24=120

Each call sits on the "call stack" waiting for the smaller call to finish. This is why recursion has O(depth) space overhead: n nested calls use n frames of stack memory.

Example 2: Fibonacci (naive and the memoization fix)

The naive recursive Fibonacci is a textbook example of how NOT to use recursion:

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

print(fib(35))     # Works but slow (~5 seconds)
print(fib(50))     # Never finishes on a laptop

Problem: fib(5) calls fib(4) and fib(3). But fib(4) ALSO calls fib(3). Same work, twice. This overlap explodes exponentially: fib(50) makes about 40 billion function calls, most of them redundant. Complexity: O(2^n).

Fix with memoization (cache results):

from functools import lru_cache

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

print(fib(100))    # Instant, correct answer

Python's @lru_cache decorator caches every unique call. Now each n is computed once. Complexity drops from O(2^n) to O(n). This is the difference between "works on a whiteboard" and "works in production".

Example 3: Binary tree in-order traversal

Trees are recursion's natural home. In-order traversal visits left subtree, current node, right subtree, in that order. For a Binary Search Tree, this produces sorted output.

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def inorder(node, result=None):
    if result is None:
        result = []
    if node is None:                    # BASE CASE: empty subtree
        return result
    inorder(node.left, result)          # left subtree
    result.append(node.value)           # current node
    inorder(node.right, result)         # right subtree
    return result

# Build tree:    4
#              /   \
#             2     6
#            / \   / \
#           1   3 5   7
root = Node(4)
root.left = Node(2); root.right = Node(6)
root.left.left = Node(1); root.left.right = Node(3)
root.right.left = Node(5); root.right.right = Node(7)

print(inorder(root))    # [1, 2, 3, 4, 5, 6, 7]

Notice how clean this is: 4 lines of logic inside inorder(). An iterative version needs an explicit stack and is 15+ lines. Recursion pays off dramatically on tree structures.

Example 4: Recursively list all files in a directory

Directories are trees. Every directory contains files + subdirectories. Recursion is the natural fit:

import os

def list_all_files(path):
    files = []
    for entry in os.listdir(path):
        full_path = os.path.join(path, entry)
        if os.path.isdir(full_path):
            files.extend(list_all_files(full_path))    # recurse into subdir
        else:
            files.append(full_path)
    return files

for f in list_all_files("/home/user/documents"):
    print(f)

Note: production code should use os.walk() which handles this iteratively under the hood (safer for very deep directory trees). But the recursive version is easier to understand and easier to modify (add a filter, transform each file, etc.).

The 2 things that break beginner recursion

Mistake 1: Missing or wrong base case. Every recursive function must have a base case that terminates without recursing. Without it, Python raises RecursionError: maximum recursion depth exceeded after about 1,000 calls:

def bad_countdown(n):
    print(n)
    bad_countdown(n - 1)   # Never stops! RecursionError.

def good_countdown(n):
    if n < 0:              # BASE CASE
        return
    print(n)
    good_countdown(n - 1)  # Terminates when n becomes negative

Mistake 2: Overlapping subproblems. If your function computes the same subproblem multiple times, you have exponential complexity. Fix with @lru_cache or convert to iteration with a table (dynamic programming, covered in the next Batch 11-C post).

When recursion is the RIGHT tool (and when it is not)

Recursion excels at problems with a recursive structure:

• Tree and graph traversal (DFS)
• Divide and conquer (merge sort, quick sort)
• Backtracking (N-Queens, sudoku solver, permutations)
• Parsing nested structures (JSON, XML, expression trees)
• Fractal generation, Koch snowflake, Sierpinski triangle

Recursion is the wrong tool for:

• Simple iteration over a flat list (use a loop)
• Deep, single-branch recursion (Python's 1,000-frame limit will hit; convert to iteration)
• Performance-critical code where iterative version is measurably faster
• Tail-recursive algorithms in Python (Python does NOT optimize tail calls; use a loop)

Python's recursion limit and how to raise it

Python defaults to 1,000 nested recursive calls. If you need more (rare, usually a sign your algorithm should be iterative):

import sys
sys.setrecursionlimit(10000)   # Now allows 10,000 nested calls

Raising the limit does not fix a broken base case, only masks it. Better fix: rewrite as iteration with an explicit stack. Any recursive function can be converted to an iterative one that uses O(1) or O(depth) stack space that YOU control instead of Python's call stack.

Related DSA + Interview tutorials

• Big-O Notation Complete Guide for Beginners 2026
• DSA Roadmap for BSIT Students 2026
• Binary Tree Complete Tutorial with Python 2026 (coming this week)
• Dynamic Programming Beginner's Guide 2026 (coming this week)

Official documentation

• Python.org: functools.lru_cache decorator
• Python.org: sys.setrecursionlimit
• Wikipedia: Recursion in computer science

Angel Jude Suarez

Full-Stack Developer at PIES IT Solution

Focuses on Python development, machine learning, and AI integration. Has built production AI systems including OpenAI Whisper integration for medical transcription and GPT-4o-powered diagnosis assistance. Strong background in pandas, scikit-learn, and TensorFlow.

Expertise: Python · PHP · Java · VB.NET · ASP.NET · Machine Learning · AI Integration · OpenCV · Django · CodeIgniter  · View all posts by Angel Jude Suarez →