Tracing recursive Python functions
Recursion in Python works exactly the same way it does in any other language: a function calls itself with a smaller input, and a base case stops the chain. Being able to trace the calls by hand is the fastest path to understanding recursive code.
Core idea
Every recursive function needs a base case that returns a value without calling itself again, and every recursive call must bring the input closer to that base case. Without both conditions, the function will recurse forever and eventually raise a RecursionError.
Two kinds of recursion
Linear recursion means the function makes exactly one recursive call per execution. The calls form a straight chain from the original call down to the base case. Classic examples include computing a factorial, summing integers from 1 to n, and raising a number to a power.
Branching recursion means the function makes two or more recursive calls per execution, forming a tree of calls. Each branch eventually reaches the base case on its own. Classic examples include Fibonacci numbers, stair-climbing counts, and grid path counts.
The call stack in Python
Python uses the same call-stack model as other languages. Each function call creates a new frame on the stack. The frame stores local variables and the point where the caller is waiting. When a function returns, its frame is removed and the caller resumes.
Python has a default recursion limit of 1000 frames. For practice problems here, inputs are chosen so no function recurses more than 10 times, keeping traces manageable to do by hand.
Call stack for factorial(4)
factorial(4) waits for factorial(3)
factorial(3) waits for factorial(2)
factorial(2) waits for factorial(1)
factorial(1) waits for factorial(0)
factorial(0) returns 1 ← base case
factorial(1) returns 1 * 1 = 1
factorial(2) returns 2 * 1 = 2
factorial(3) returns 3 * 2 = 6
factorial(4) returns 4 * 6 = 24
Worked examples
Example 1: linear recursion — sum_nums(5)
This function adds all positive integers from 1 up to n.
def sum_nums(n):
if n == 0:
return 0
return n + sum_nums(n - 1)Trace of sum_nums(5):
sum_nums(5) = 5 + sum_nums(4) sum_nums(4) = 4 + sum_nums(3) sum_nums(3) = 3 + sum_nums(2) sum_nums(2) = 2 + sum_nums(1) sum_nums(1) = 1 + sum_nums(0) sum_nums(0) = 0 ← base case Unwinding: sum_nums(1) = 1 + 0 = 1 sum_nums(2) = 2 + 1 = 3 sum_nums(3) = 3 + 3 = 6 sum_nums(4) = 4 + 6 = 10 sum_nums(5) = 5 + 10 = 15
Example 2: branching recursion — fib(5)
The Fibonacci function makes two recursive calls per step, producing a call tree.
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)Key values (build up from the base cases):
fib(0) = 0 fib(1) = 1 fib(2) = fib(1) + fib(0) = 1 fib(3) = fib(2) + fib(1) = 2 fib(4) = fib(3) + fib(2) = 3 fib(5) = fib(4) + fib(3) = 5
Example 3: string recursion
Recursion works just as well on strings. Instead of decrementing an integer, the function shortens the string by one character each call using the s[1:] slice, which drops the first character. The base case is an empty string, which is falsy in Python (if not s).
The function below counts the length of a string, and the one after it reverses a string — both by peeling off one character per call.
def length(s):
if not s:
return 0
return 1 + length(s[1:])
def rev(s):
if not s:
return ""
return rev(s[1:]) + s[0]Trace of length("cat"):
length("cat") = 1 + length("at")
length("at") = 1 + length("t")
length("t") = 1 + length("")
length("") = 0 ← base case
Unwinding:
length("t") = 1 + 0 = 1
length("at") = 1 + 1 = 2
length("cat") = 1 + 2 = 3
Trace of rev("cat"):
rev("cat") = rev("at") + "c"
rev("at") = rev("t") + "a"
rev("t") = rev("") + "t"
rev("") = "" ← base case
Unwinding:
rev("t") = "" + "t" = "t"
rev("at") = "t" + "a" = "ta"
rev("cat") = "ta" + "c" = "tac"
Notice that rev returns a string, not an integer. The practice questions will tell you the return type — read the function signature carefully before you answer.
Avoiding infinite recursion in Python
Python raises a RecursionError: maximum recursion depth exceeded when the call stack grows beyond its limit. The same two mistakes cause this as in any language:
- The recursive call does not make the input smaller, so the base case is never reached.
- The base case condition is incorrect or missing entirely.
All practice problems on this site guarantee termination within ten recursive steps, so you can trace them by hand or run them safely in a Python interpreter.
Refreshable sample
Try one Python recursion question
Select linear or branching style, trace the function on paper, then enter your answer and check it.
Why this skill matters
Recursive thinking underlies sorting algorithms, tree traversal, graph search, dynamic programming, and many interview problems. Practicing the trace by hand cements your understanding of how the call stack works and makes it much easier to debug recursive code when something goes wrong.
After you are comfortable tracing these introductory functions, the same technique applies to more complex problems like merge sort, binary search trees, and backtracking.
If you also work in Java, the Java recursion tutorial covers the same examples with Java method syntax — a useful reference if you move between both languages.
Open Python recursion practice