Skip to content
Python

Python Recursion: Base Case, Call Stack and RecursionError

Ihsan Ullah · 11 min read
Python recursion, Lesson 26 of the Python course: base case, call stack and RecursionError

Python course · Module 5: Functions · Lesson 26 of 63

Quick answer: Recursion means a function calls itself to solve a smaller version of the same problem. Every recursive function needs a base case, a simple input it answers directly without calling itself, and a recursive case that moves closer to the base case, as in return n * factorial(n - 1). If the base case is missing or never reached, Python stops with RecursionError: maximum recursion depth exceeded. sys.getrecursionlimit() shows the limit, 1000 in our runs.

In this lesson you will learn:

  • what a base case and a recursive case are
  • how to write factorial and the sum of a nested list with recursion
  • what the call stack is and how recursive calls wait for each other
  • why RecursionError happens and what sys.getrecursionlimit() shows
  • when a loop is a better choice than recursion

Before you start: finish Lesson 25, Python Lambda Functions: sorted() with key, map() and filter(). You need def and return from Lesson 22 and local variables from Lesson 24. All examples were tested on Python 3.14.6 and gave exactly the same output on Python 3.15.2, the newest release on python.org.

A function that calls itself

A countdown is the smallest example. To count down from 3, print 3 and then count down from 2:

def countdown(n):
    if n == 0:
        print("Go!")
        return
    print(n)
    countdown(n - 1)

countdown(3)
3
2
1
Go!

countdown(3) prints 3 and calls countdown(2), which prints 2 and calls countdown(1), and so on. When n reaches 0, the function prints Go! and returns without calling itself again. That stop is what makes the program end.

Base case and recursive case

Every recursive function has two parts:

  • The base case is an input so simple that the function answers it directly. In countdown(), it is n == 0.
  • The recursive case calls the function again with a smaller input, so each call gets closer to the base case. In countdown(), it is countdown(n - 1).

Factorial is the classic example. The factorial of 5, written 5!, is 5 × 4 × 3 × 2 × 1 = 120, which is 5 × 4!. So the factorial of n is n times the factorial of n - 1, and the factorial of 1 is simply 1:

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

for n in range(1, 7):
    print(n, factorial(n))
1 1
2 2
3 6
4 24
5 120
6 720
  • if n <= 1: return 1 is the base case.
  • return n * factorial(n - 1) is the recursive case. n - 1 is smaller, so it always moves towards 1.

We wrote n <= 1, not n == 1, on purpose: the factorial of 0 is also 1, and n <= 1 handles it.

The call stack, explained simply

How can factorial(4) work if it needs factorial(3) first? Python keeps a call stack: a pile of the function calls that have started but not finished yet. Each call gets its own copy of n and its other local variables. The Python tutorial says: “When a function calls another function, or calls itself recursively, a new local symbol table is created for that call.”

This version prints a line when each call starts and when it returns. The extra parameter depth has a default value (Lesson 23) and only adds spaces to show how deep each call is:

def factorial(n, depth=0):
    pad = "    " * depth
    print(f"{pad}factorial({n}) starts")
    if n <= 1:
        print(f"{pad}factorial({n}) returns 1")
        return 1
    result = n * factorial(n - 1, depth + 1)
    print(f"{pad}factorial({n}) returns {result}")
    return result

print("Answer:", factorial(4))
factorial(4) starts
    factorial(3) starts
        factorial(2) starts
            factorial(1) starts
            factorial(1) returns 1
        factorial(2) returns 2
    factorial(3) returns 6
factorial(4) returns 24
Answer: 24
Python recursion call stack diagram from Lesson 26: factorial(4) calls factorial(3), which calls factorial(2), which calls factorial(1); factorial(1) returns 1, then the results 2, 6 and 24 come back down the stack.
Each recursive call waits on the call stack until the call above it returns. factorial(1) is the base case, and the answers 1, 2, 6 and 24 flow back down.

Read the output from the top:

  1. Calls pile up. factorial(4) cannot finish until it knows factorial(3), so it pauses and a new call goes on top of the stack. The same happens for 3 and 2.
  2. The base case. factorial(1) returns 1 straight away. It is the first call to finish and leaves the stack.
  3. Answers come back. factorial(2) gets the 1 and returns 2 × 1 = 2. Then factorial(3) returns 3 × 2 = 6, and factorial(4) returns 4 × 6 = 24.

The last call that started is the first to finish, like a pile of plates. That is also why a traceback lists every call that was still waiting.

Sum of a nested list

Recursion is most useful for data that has the same shape inside itself. Imagine an order where some items come in boxes, and some boxes hold smaller boxes. A for loop (Lesson 12) can add numbers, but it cannot know how deep the boxes go. Recursion can: when an item is a list, sum that list in the same way.

To ask “is this item a list?”, use the built-in isinstance(). The built-in functions page says it returns True “if the object argument is an instance of the classinfo argument”:

def nested_sum(items):
    total = 0
    for item in items:
        if isinstance(item, list):
            total = total + nested_sum(item)
        else:
            total = total + item
    return total

print(nested_sum([450, 60, 40]))
print(nested_sum([450, [60, 60], [40, [25, 25]], 3200]))
print(isinstance([60, 60], list), isinstance(450, list))
550
3860
True False
  • The base case here is a number: it is simply added.
  • The recursive case is a list inside the list: nested_sum(item) adds up that smaller list first.
  • [40, [25, 25]] is handled by a call that itself makes another call for [25, 25]. The total is 450 + 120 + 90 + 3200 = 3860.

RecursionError: when recursion never stops

Remove the base case from factorial and the calls never end:

def factorial(n):
    return n * factorial(n - 1)

print(factorial(5))
Traceback (most recent call last):
  File "/home/learner/python-course/err1_no_base_case.py", line 4, in <module>
    print(factorial(5))
          ~~~~~~~~~^^^
  File "/home/learner/python-course/err1_no_base_case.py", line 2, in factorial
    return n * factorial(n - 1)
               ~~~~~~~~~^^^^^^^
  File "/home/learner/python-course/err1_no_base_case.py", line 2, in factorial
    return n * factorial(n - 1)
               ~~~~~~~~~^^^^^^^
  File "/home/learner/python-course/err1_no_base_case.py", line 2, in factorial
    return n * factorial(n - 1)
               ~~~~~~~~~^^^^^^^
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

factorial(5) calls factorial(4), then 3, 2, 1, 0, -1 and so on, with nothing to stop it. Every waiting call stays on the stack, so Python stops the program when the stack gets too deep. The traceback shows the line three times and then says [Previous line repeated 996 more times]. The exceptions page says RecursionError is raised “when the interpreter detects that the maximum recursion depth … is exceeded”.

sys.getrecursionlimit()

The sys module tells you the limit. The import sys line loads it; Lesson 27 explains imports.

import sys

print(sys.getrecursionlimit())
1000

Both Python 3.14.6 and 3.15.2 printed 1000 in our runs. The sys docs describe it as “the maximum depth of the Python interpreter stack” and say it “prevents infinite recursion from causing an overflow of the C stack and crashing Python”.

The limit also stops recursion that is correct but too deep. This function adds up the numbers from 1 to n:

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

print(total_to(100))
print(total_to(900))
print(total_to(5000))
5050
405450
Traceback (most recent call last):
  File "/home/learner/python-course/step6_total_to.py", line 8, in <module>
    print(total_to(5000))
          ~~~~~~~~^^^^^^
  File "/home/learner/python-course/step6_total_to.py", line 4, in total_to
    return n + total_to(n - 1)
               ~~~~~~~~^^^^^^^
  File "/home/learner/python-course/step6_total_to.py", line 4, in total_to
    return n + total_to(n - 1)
               ~~~~~~~~^^^^^^^
  File "/home/learner/python-course/step6_total_to.py", line 4, in total_to
    return n + total_to(n - 1)
               ~~~~~~~~^^^^^^^
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

The base case is fine, but total_to(5000) needs 5001 calls waiting at the same time. In our test, the largest n that worked was 998. sys.setrecursionlimit() can raise the limit, but the sys docs warn that “a too-high limit can lead to a crash”.

When to use a loop instead

The same total with a for loop has no depth problem, because the loop does not pile up calls:

def total_to(n):
    total = 0
    for k in range(1, n + 1):
        total = total + k
    return total

print(total_to(100))
print(total_to(5000))
print(total_to(1000000))
print(sum(range(1, 5001)))
5050
12502500
500000500000
12502500

A million numbers are no problem, and the built-in sum() does it in one line. Factorial is just as easy with a loop:

def factorial_loop(n):
    result = 1
    for k in range(2, n + 1):
        result = result * k
    return result

print(factorial_loop(6))
print(factorial_loop(20))
720
2432902008176640000

A simple rule of thumb:

  • Use a loop when you walk through items one after another, like counting, totals or a list of prices. A loop has no depth limit.
  • Use recursion when the data has parts of the same shape inside it, like nested lists or folders, and the depth is small. The code is often shorter and closer to how you describe the problem.

Try it yourself

Exercise 1: Power

Write a recursive function power(base, exponent) that returns base multiplied by itself exponent times. Use exponent == 0 as the base case (anything to the power 0 is 1). Test power(2, 10), power(5, 3) and power(7, 0).

Exercise 2: Count items in nested lists

Write count_items(items) that counts all the items in a list, including items inside inner lists, but not the inner lists themselves. ["Pen", ["Notebook", "Ruler"], [["Eraser"], "Marker"]] should give 5.

Exercise 3: Digit sum

Write a recursive digit_sum(n) that adds up the digits of a positive whole number, so digit_sum(4507) gives 16. Hint: with % and // from Lesson 6, n % 10 is the last digit and n // 10 removes it.

Solutions

Solution 1

def power(base, exponent):
    if exponent == 0:
        return 1
    return base * power(base, exponent - 1)

print(power(2, 10))
print(power(5, 3))
print(power(7, 0))
1024
125
1

Each call lowers exponent by one until it reaches the base case, 0.

Solution 2

def count_items(items):
    count = 0
    for item in items:
        if isinstance(item, list):
            count = count + count_items(item)
        else:
            count = count + 1
    return count

print(count_items(["Pen", ["Notebook", "Ruler"], [["Eraser"], "Marker"]]))
print(count_items([]))
5
0

This is nested_sum() again, but each non-list item adds 1 instead of its value.

Solution 3

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

print(digit_sum(4507))
print(digit_sum(9))
16
9

A one-digit number is its own digit sum (the base case); otherwise add the last digit to the digit sum of the rest.

Common mistakes

  • No base case. The function calls itself forever and stops with RecursionError: maximum recursion depth exceeded. Write the base case first.
  • A base case that is never reached. With if n == 1: return 1, the call factorial(0) goes 0, -1, -2 and ends with the same RecursionError. Use n <= 1, or check for bad input.
  • Forgetting return in the recursive case. Writing n * factorial(n - 1) without return makes the function return None, and the caller fails with TypeError: unsupported operand type(s) for *: 'int' and 'NoneType'.
  • Raising the recursion limit as a fix. It hides the real problem and can crash Python. Fix the base case, or use a loop.

Frequently asked questions

What is a base case in recursion?

The base case is the input a recursive function answers directly, without calling itself. In factorial it is n <= 1, which returns 1. Without a base case that is always reached, the function never stops and ends with RecursionError.

What is the maximum recursion depth in Python?

sys.getrecursionlimit() returns it, and it printed 1000 on Python 3.14.6 and 3.15.2 in our runs. A little less is available to your own function, because the main program is already on the stack: our total_to() worked up to 998.

How do I fix RecursionError: maximum recursion depth exceeded?

First check the base case: is there one, and does every call move closer to it? If the logic is correct but the input is very large, rewrite the function with a loop, as we did with total_to(). Raise the limit with sys.setrecursionlimit() only with care, because a too-high limit can crash Python.

Summary

  • A recursive function needs a base case that stops it and a recursive case that moves towards it.
  • Each call has its own local variables and waits on the call stack until the calls above it return.
  • Recursion suits nested data, like the sum of a nested list, where the depth is unknown but small.
  • A missing or unreachable base case, or very deep input, gives RecursionError; sys.getrecursionlimit() printed 1000 in our runs.
  • Use a loop for long, flat tasks like totals and counting.

Next lesson

Next: Lesson 27, Python Modules: import and the Standard Library.

Sources

Ihsan Ullah

Written & tested by Ihsan Ullah

Data analyst with 3 years of experience and a Bachelor's degree in Computer Science. I write clear, practical guides on data, SQL, Python and AI.

More about me →

Leave a comment

Your email address will not be published. Required fields are marked *