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
RecursionErrorhappens and whatsys.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.
Table of Contents
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 isn == 0. - The recursive case calls the function again with a smaller input, so each call gets closer to the base case. In
countdown(), it iscountdown(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 1is the base case.return n * factorial(n - 1)is the recursive case.n - 1is 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

Read the output from the top:
- Calls pile up.
factorial(4)cannot finish until it knowsfactorial(3), so it pauses and a new call goes on top of the stack. The same happens for 3 and 2. - The base case.
factorial(1)returns 1 straight away. It is the first call to finish and leaves the stack. - Answers come back.
factorial(2)gets the 1 and returns 2 × 1 = 2. Thenfactorial(3)returns 3 × 2 = 6, andfactorial(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 callfactorial(0)goes 0, -1, -2 and ends with the sameRecursionError. Usen <= 1, or check for bad input. - Forgetting
returnin the recursive case. Writingn * factorial(n - 1)withoutreturnmakes the function returnNone, and the caller fails withTypeError: 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
- Defining functions: a new local symbol table for each call (Python tutorial)
- sys.getrecursionlimit() and sys.setrecursionlimit() (Python docs)
- Built-in Exceptions: RecursionError (Python docs)
- Built-in Functions: isinstance() (Python docs)
- Python downloads page (python.org)





