Course topics

By WebNest Studio Engineering Team

Python Tutorial

Recursion in Python

A recursive function solves a problem by calling itself on a smaller version of the same problem. Many problems are naturally recursive: factorials, walking nested folders or JSON, tree and graph traversal, divide-and-conquer sorting, generating permutations.

This lesson covers base cases and recursive cases, how the call stack works, Python's recursion limit, memoization with functools.lru_cache, recursion over nested data, and when an iterative solution is better.

Why it matters

Some data is nested to an unknown depth: folders inside folders, comments with replies, JSON inside JSON. A function that calls itself handles each level in the same way, however deep the data goes, and is the natural way to write tree and graph algorithms. Recursion is also a standard interview topic.

Base Case and Recursive Case

Every recursive function needs a base case that returns without recursing, and a recursive case that moves toward it. Missing or unreachable base cases cause infinite recursion, which Python stops with RecursionError.

The Call Stack and the Recursion Limit

Each call gets its own frame on the call stack with its own local variables. Python limits the depth (1000 frames by default, see sys.getrecursionlimit()) and does not optimise tail calls, so very deep recursion should be rewritten as a loop.

Memoization

Naive recursive Fibonacci recomputes the same values exponentially many times. Caching results — memoization — with @functools.lru_cache or @functools.cache turns it into a linear-time algorithm with one line.

Examples

Factorial, sum of digits and power

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

def digit_sum(n):
    return n if n < 10 else n % 10 + digit_sum(n // 10)

def power(base, exp):
    if exp == 0:
        return 1
    half = power(base, exp // 2)
    return half * half * (base if exp % 2 else 1)

print(factorial(5), digit_sum(98765), power(2, 30))
Output
120 35 1073741824

Memoized Fibonacci and the recursion limit

Python
import sys
from functools import lru_cache

calls = 0
def fib_slow(n):
    global calls
    calls += 1
    return n if n < 2 else fib_slow(n - 1) + fib_slow(n - 2)

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

print(fib_slow(20), "calls:", calls)
print(fib_fast(90))
print(fib_fast.cache_info().misses, "distinct values computed")
print("limit:", sys.getrecursionlimit())

def countdown(n):
    return countdown(n - 1)          # no base case!
try:
    countdown(5)
except RecursionError as e:
    print("RecursionError:", e)
Output
6765 calls: 21891
2880067194370816120
91 distinct values computed
limit: 1000
RecursionError: maximum recursion depth exceeded

Recursion over nested data and permutations

Python
def flatten(items):
    result = []
    for item in items:
        if isinstance(item, list):
            result.extend(flatten(item))
        else:
            result.append(item)
    return result

def count_keys(data):
    if isinstance(data, dict):
        return len(data) + sum(count_keys(v) for v in data.values())
    if isinstance(data, list):
        return sum(count_keys(v) for v in data)
    return 0

def permutations(s):
    if len(s) <= 1:
        return [s]
    return [ch + p for i, ch in enumerate(s) for p in permutations(s[:i] + s[i + 1:])]

print(flatten([1, [2, [3, [4, 5]]], 6]))
print(count_keys({"a": 1, "b": {"c": 2, "d": [{"e": 3}]}}))
print(permutations("abc"))
Output
[1, 2, 3, 4, 5, 6]
5
['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

Common Mistakes

  • Forgetting the base case or never moving toward it.
  • Using naive recursion for overlapping subproblems without memoization.
  • Recursing thousands of levels deep in Python instead of using a loop.
  • Raising the recursion limit with sys.setrecursionlimit to hide a design problem.

Exercise

Write a recursive factorial function. Then write a recursive flatten function that turns a list containing nested lists into one flat list.

Expected output: 120 then [1, 2, 3, 4, 5]

Python · starter code
def factorial(n):
    # TODO: base case, then the recursive case
    pass


def flatten(items):
    # TODO: for each item, flatten it if it is a list, otherwise keep it
    pass


print(factorial(5))
print(flatten([1, [2, [3, 4]], 5]))
Show hints
  • The base case for factorial is n <= 1, which returns 1. Otherwise return n * factorial(n - 1).
  • In flatten, use isinstance(item, list) to decide, and result.extend(flatten(item)) for a nested list.
Show solution
Python · solution
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)


def flatten(items):
    result = []
    for item in items:
        if isinstance(item, list):
            result.extend(flatten(item))
        else:
            result.append(item)
    return result


print(factorial(5))
print(flatten([1, [2, [3, 4]], 5]))

Quick quiz

1. What happens when a recursive function has no base case?

  • A. It returns None
  • B. It runs forever without error
  • C. It runs until RecursionError is raised
  • D. It does not compile
Show answer

C. Python stops the calls when the recursion limit is exceeded.

2. About how deep can recursion go in Python by default?

  • A. 100 calls
  • B. There is no limit
  • C. 1,000,000 calls
  • D. 1,000 calls
Show answer

D. The default limit is 1000 and can be read with sys.getrecursionlimit().

3. Which decorator stores the results of previous calls so they are not computed again?

  • A. @functools.lru_cache
  • B. @staticmethod
  • C. @property
  • D. @classmethod
Show answer

A. Caching results in this way is called memoization.

Interview questions

What are the parts of a recursive function?

Show answer

A base case, which returns a result directly without another call and so ends the recursion, and a recursive case, which calls the function again with an input that is closer to the base case. Each call must make progress towards the base case, or the recursion never ends.

When is recursion a poor choice in Python?

Show answer

When the depth can be large. Each call uses a stack frame, Python limits the depth to about a thousand calls, and it does not optimise tail calls, so a deep recursion fails where a loop would not. Recursion that recomputes the same values, as in a plain Fibonacci, is also very slow unless the results are cached. A simple linear repetition is better written as a loop.

Key Points to Remember

  • Recursion needs a base case and a recursive case that shrinks the problem.
  • Each call has its own stack frame; Python's default depth limit is 1000.
  • @lru_cache / @cache memoize results to avoid repeated work.
  • Recursion suits nested data, trees and divide-and-conquer; loops suit deep linear repetition.

Practice in the playground

Write and run your own code for this topic, or start from the exercise or an example. Runs Python in your browser. Your code for each topic is kept in this browser.

Run the examples

Change an input, predict the result, then compare it with the output. Explain why the result changes.

WebNest Studio

Written by

WebNest Studio Engineering Team

Practical lessons from developers working with Java, Python, React, databases and production systems.

Led by Vansh Duggal, Founder, WebNest Studio · Full-stack & software engineering