Understand Recursion and the Call Stack
Trace recursive calls and write a function that stops correctly for empty and nested input.
Example check: Worked and guided code samples are checked against CPython 3.13. Practice uses Pyodide 0.29.5 (Python 3.13) in your browser. How we check lessons
Video lesson: Understand Recursion and the Call Stack
The preview is stored on this site. YouTube loads only when you press Play. Watch on YouTube
Jump to a chapter
Read the video transcript
Select a timestamp to watch that moment on YouTube.
- 00:00
A list can contain more lists, and those lists can contain even more lists. A single flat loop sees the outer items, but one of those items is itself another problem of the same kind. Recursion lets a function call itself on that smaller nested list. It sounds mysterious until you follow two rules: say exactly when the function stops, and make every recursive call work on a smaller piece. Today we will deliberately break those rules, read the resulting Python error, and then repair the function. We will trace both the trip down the call stack and the return values on the way back up. Finally, we will build a sum for nested lists that handles empty lists, negative numbers, and repeated calls without changing its input.
- 00:46
The companion PythonLessonLab lesson has a browser console, three worked examples, a checked practical task, common mistakes, and a quiz. Before we run anything, predict the total of this input. The visible numbers are two, three, negative one, four, and five. Their sum should be thirteen. A good implementation should return thirteen from the function, not merely print the right number once. Returning a result lets a parent recursive call use it. The base case looks reasonable: an empty list has length zero. But the recursive call receives exactly the same nonempty list. It never moves toward the empty-list case.
- 01:27
Each call waits for another call, which waits for another, and Python eventually stops the chain with RecursionError. The error is a protection against an ever-growing call stack, not a cue to increase the recursion limit for this mistake. We need to change the algorithm. For a simple count, the smaller problem is the list without its first item. Passing `items[1:]` moves toward the empty base case. In a nested-list sum, the smaller problem is each nested list found inside the current list. The same idea applies, even though the input does not shrink by slicing. The function works on a contained substructure and returns a subtotal to its parent.
- 02:09
When debugging recursion, ask what exactly is different between the current call and the next call. If the answer is nothing, the code is probably wrong. A base case that exists in source code is not enough; the recursive path must be able to reach it. Also think about your input contract. The broken count would behave differently for negative numbers because it was written for lists, not for arbitrary numeric values. Base cases need to match the data they actually receive. This function goes in at one, then two, then three. At three it does not call itself again. That is the base case. The call for two can now finish: two plus the returned three is five.
- 02:53
Only then can the call for one finish: one plus five is six. The return lines appear in the opposite order from the calls because each parent was waiting on its child. Every call has its own local number and result; there is no single result variable being overwritten by all calls. This is what the call stack tracks. You can often understand recursion by writing a small table with current input, child input, child return, and final return. Use a tiny input first; a stack of four or five calls is much easier to reason about than a hundred. Notice that the function returns a number at every branch. If we called the child but ignored its return, the parent would have no way to combine the smaller answer.
- 03:39
That will matter in our nested-list task. Also notice that this particular function only has a base case at three. Calling it with four would keep increasing forever. A correct function needs a base case that all supported inputs can reach. In real code, validate unsupported inputs or choose a recursive direction that clearly reduces a measured size. We initialize a fresh local total for each call. If the item is an integer, we add it directly. If the item is a list, we call the same function on that smaller nested list and add its returned subtotal. The empty-list base case is hidden in plain sight: with no items, the loop runs zero times and returns the initial zero.
- 04:25
The inner list containing three and negative one returns two. The deepest list containing five returns five, so its parent containing four and that list returns nine. Finally, the outer call adds two, two, and nine to get thirteen. The original list prints exactly as it began because the function only reads it. This approach handles any reasonable nesting depth allowed by Python's recursion limit, but it does not promise to handle a million nested lists. Deep recursion uses stack memory. A very deep tree can be traversed with an explicit stack in a loop instead. Do not raise the recursion limit merely to make an accidental infinite recursion run longer.
- 05:08
The function contract here says every non-list item is an integer. If data comes from an external source, you may need to reject strings, booleans, or malformed nested values before summing. For the lesson task, focus on the stated input shape and the clear return path. The checks exercise the real boundary conditions. An empty list returns zero. A nested empty list also contributes zero, while a negative number subtracts from the total. Four levels of nesting still give the right sum. The input remains unchanged after a call. A later independent call returns eight; that would expose a shared global accumulator that accidentally carried the previous answer forward.
- 05:54
These assertions cannot prove the function will handle every possible input or an extreme stack depth, but they cover the behavior promised by this small exercise. Now open the matching PythonLessonLab page. Click Try this example on the worked snippets, complete the practical function, and run the task checker before answering the quiz. If a check fails, do not immediately copy the solution. Trace one nested branch and write down what it returns to its parent. Most recursion bugs become clear when you identify an unreachable base case or a returned value that was discarded. The core pattern is simple: define the smallest answer, reduce the problem, and combine the smaller answer on the way back.
- 06:40
Once you can see that flow in a nested list, recursive directory trees, expression trees, and nested JSON become much easier to read. Use recursion when the data shape justifies it, and prefer an ordinary loop when a flat sequence is already simple.
Understand the concept
A recursive function calls itself on a smaller part of the problem. Each call has its own local variables and waits on the call stack for its child call to return. The base case is the input small enough to answer directly. Without a base case, or without progress toward it, calls continue until Python raises RecursionError. Recursion is a way to express naturally nested data; it is not a universal replacement for a loop.
For a nested list such as [2, [3, 4], 5], the function can inspect each item. A number contributes itself; a list contributes the result of a recursive call on that list. The empty list contributes zero. The value returned by a child call is added to its parent call's total, then the parent eventually returns its own total. Write down those intermediate returns before running code to make the stack less mysterious.
A common mistake is to recurse on the same input instead of a smaller piece, or to forget to use the returned value. Another is to mutate the list while traversing it, which can skip items and makes repeated calls surprising. This lesson's function only reads the input and returns a number. Nested lists can be arbitrarily deep in the data model, but Python imposes a finite recursion limit; very deep structures may need an explicit stack instead.
In the checked exercise, implement sum_nested(items) for integers and nested lists of integers. Return zero for an empty list, preserve negative values, and leave the input untouched. The prepared example reaches two recursive branches. The hidden cases also test several nesting depths and independent repeated calls so a stale shared accumulator cannot accidentally pass.
- A base case ends recursion
- Each call has its own local state on the call stack
- A recursive step must make progress toward a base case
- Very deep recursion can raise RecursionError
See it step by step
Read the code, predict the output, then compare it with the result.
01. Watch recursive calls return
def countdown(number):
if number == 0:
return "go"
return f"{number}, " + countdown(number - 1)
print(countdown(3))3, 2, 1, goEach call waits for the smaller call to return; zero is the base case.
02. Add a nested list without changing it
def total(values):
answer = 0
for value in values:
answer += total(value) if isinstance(value, list) else value
return answer
data = [2, [3, -1], [4, [5]]]
print(total(data))
print(data)13
[2, [3, -1], [4, [5]]]Nested lists are smaller subproblems. The parent adds each returned total and leaves the original data intact.
03. See local values on the way back
def add_to_three(number):
if number == 3:
print("base", number)
return number
result = number + add_to_three(number + 1)
print("return", number, result)
return result
print("total", add_to_three(1))base 3
return 2 5
return 1 6
total 6The deepest call finishes first; then the waiting calls resume in reverse order.
A closer look
Follow the reasoning, inspect each result, then try the suggested changes in the console below.
Follow calls down to the base case
The important question in a recursive function is not how many times it calls itself; it is what happens on the smallest input. Here countdown stops at zero. Every other call reduces number by one, so it will eventually reach that base case when it starts with a nonnegative integer. Each call waits while the next call finishes. The stack therefore grows on the way down and unwinds on the way back up.
Read the output before running the code. The entering lines run in descending order because they happen before the recursive call. The leaving lines run in ascending order because each parent resumes only after its child returns. Change the starting value from 3 to 1 and predict the new order. Do not try a negative start with this base case: decrementing a negative value would move farther away from zero.
def countdown(number):
print("enter", number)
if number == 0:
print("base")
return
countdown(number - 1)
print("leave", number)
countdown(3)enter 3
enter 2
enter 1
enter 0
base
leave 1
leave 2
leave 3- The first call prints enter 3 and waits for countdown(2).
- At zero, the base case returns without another call.
- Waiting parent calls resume in reverse order and print their leave lines.
Return a value to the waiting parent
A recursive call can do more than print. It can return an answer for a smaller subproblem, which the parent combines with its own contribution. In triangular(4), the parent needs 4 plus triangular(3). The smaller function needs 3 plus triangular(2), and so on. When triangular(0) returns zero, the waiting calls can finally compute 1, then 3, then 6, then 10.
Notice that result is local to each call. There is no global total to reset, so triangular(4) and triangular(2) can be called independently. This is why returning values is usually easier to reason about than changing a shared global accumulator. Recursion still uses stack frames; a huge input is better handled with a loop or a mathematical formula. For our nested-list exercise, the shape of the data is the reason recursion is useful.
def triangular(number):
if number == 0:
return 0
return number + triangular(number - 1)
print(triangular(4))
print(triangular(2))10
3- triangular(0) returns zero directly.
- Each parent adds its own number to the child result.
- A second call starts with fresh local frames and returns three.
Let the data shape define the recursive step
A list may contain both numbers and more lists. The natural rule is: a number contributes its value; a list contributes the sum of its contents. Applying that rule to a nested list gives the same function for every depth. The empty list returns zero because the loop has nothing to add. A negative number contributes a negative amount without any special recursion branch.
The function only reads items. It neither flattens the original list in place nor saves a shared accumulator. In the practice task, use this exact decomposition and then run the checks for empty input, multiple depths, and repeated calls. If an item can be another kind of value in your real program, decide whether to reject it or transform it at the boundary; the lesson's contract is integers and nested lists of integers.
def sum_nested(items):
total = 0
for item in items:
if isinstance(item, list):
total += sum_nested(item)
else:
total += item
return total
data = [2, [3, -1], [4, [5]]]
print(sum_nested(data))
print(sum_nested([]))
print(data)13
0
[2, [3, -1], [4, [5]]]- Each nested list becomes a smaller call of the same function.
- The parent adds the returned subtotal to its local total.
- The input stays unchanged and an empty list naturally returns zero.
Try it in Python
Edit the example and run it. Python starts in your browser the first time you click Run.
Python console
Ready to runNeed input()? Add one value per line
Your output appears here.
Need a hint?
Start total = 0. Loop over items. If isinstance(item, list), add sum_nested(item); otherwise add item. Return total after the loop. The empty list needs no special branch because the loop runs zero times.
Complete the task and select Check task to verify your code.
Quick quiz
Three questions. You can change your answers and try again.
Typical mistakes
Everyone meets these errors. See what causes them and how to fix them.
Recursing on the unchanged input
def length(items):
if not items: return 0
return 1 + length(items)def length(items):
if not items: return 0
return 1 + length(items[1:])What happens: The input never shrinks, so calls end in RecursionError.
Each recursive call must move closer to the empty-list base case.
Ignoring the child's return value
if isinstance(item, list):
sum_nested(item)if isinstance(item, list):
total += sum_nested(item)What happens: Numbers inside nested lists never contribute to the parent total.
The parent must use the value returned by its child call.
Sharing an accumulator between calls
total = 0
def sum_nested(items):
global total
for item in items: total += item
return totaldef sum_nested(items):
total = 0
for item in items:
total += sum_nested(item) if isinstance(item, list) else item
return totalWhat happens: A second call starts from the first call's answer and nested lists are not handled.
A local total belongs to each call and is combined by returned values.