The call stack and argument passing in Python

Why it matters

Two surprises come up again and again with functions. The first is "why did my swap function not swap anything?" The second is "what does RecursionError mean?" The answers come from the same place: how Python runs calls and passes arguments. Once you can picture the call stack, you can trace programs with nested or recursive calls, predict when a value changes, and read the traceback that Python prints when something goes wrong. Interviewers ask about recursion and about argument passing often, and the two questions are closely linked.

The idea: a stack of frames

When a function is called, Python creates a frame. A frame is the record for one call. It holds that call's parameters and local names, and it remembers where to continue when the call ends. Frames are kept on a structure called the call stack.

A stack works like a pile of plates. A new call puts a frame on top. A return takes the top frame off. Python never takes a frame from the middle. The frame on top is the function that is running now, and the frames below it are waiting for a result.

Think of a pile of forms waiting for signatures. A manager receives a request, and before she signs it she asks an assistant to check a detail. The assistant puts a new form on top of the pile, and the manager cannot sign her own form until the assistant returns. Each form is one call. When the top form is done, it is removed, and the form below continues.

Here is a program with three levels of calls. Predict the output before you read on.

Output:

main start
a start
in b
a end
main end

The stack changes at each call and each return. The table shows its state, with the top frame listed first.

While b runs, a and main are still on the stack, waiting. A frame is removed only when its function returns, so the callers stay where they are until then.

What a frame holds

Each frame holds three kinds of information. It holds the parameters of the call, such as n in factorial(n). It holds the local names the function creates. It also holds the place to continue in the caller once the call returns.

Each call has its own frame, so each call has its own parameters and locals. Two calls to the same function never share their locals. This is why a recursive function can use the same names at every level without a clash. Each level has its own n.

You do not see frames in normal code. Python keeps them for you, and a traceback (Python's error report) is the one place where they show up in text.

Recursion on the stack

A function can call itself. This is called recursion. Each call to itself creates a new frame on top of the previous one. The frames build up as the problem is broken into smaller pieces, and then the answers come back up the chain one by one.

Here is the factorial function. The factorial of a number is the product of all whole numbers from 1 up to that number. The factorial of 5 is 1 times 2 times 3 times 4 times 5, which is 120.

Output:

120
265252859812191058636308480000000

The if is the base case. When n is 1 or less, the function returns 1 without calling itself, and the chain stops. Every other call returns n multiplied by the answer for n - 1.

Python integers have no fixed size limit. factorial(30) is a 33-digit number, and Python prints every digit. Languages with fixed-size integers would overflow long before that.

Trace factorial(3). The top-level code calls factorial(3), so the stack holds that frame and the top-level frame. Inside it, 3 * factorial(2) needs factorial(2), so that frame is pushed. Then 2 * factorial(1) needs factorial(1), and that frame is pushed too. Now factorial(1) hits the base case and returns 1, and its frame is removed. factorial(2) receives 1, computes 2, returns it and is removed. factorial(3) receives 2, computes 6, returns it and is removed. The top-level code receives 6.

Recursion always has two phases. On the way down, each call hands a smaller problem to the next call, and the stack grows. On the way up, each call combines its answer with the answer it received, and the stack shrinks. A recursive function is correct only when both phases are correct, and the base case is what ends the way down.

Recursion over a list

Recursion is not only for numbers. A common pattern walks through a list one item at a time. Each call handles one item and passes the rest to the next call.

One way is to pass the list and an index, which is the position of the item being handled. The base case is the index reaching the end of the list.

Output:

24
24
[3, 5, 7, 9]

In sum_from, the index moves one step toward len(nums), and the base case is the index reaching it. The list never changes, and only i differs from call to call.

sum_list uses a different style. The slice nums[1:] makes a new list that holds every item except the first. Each call then works on a shorter list. The code reads more simply, but each slice copies the rest of the list. For a list of ten thousand items, the copies add up. The index version avoids the copies. In real code, you would use sum(data) for this task, and the recursive versions are here to show the stack.

Trace sum_from on [3, 5, 7, 9]. The first frame reads 3 and waits for the frame at index 1. That frame reads 5 and waits for index 2. That one reads 7 and waits for index 3. The frame at index 3 reads 9 and waits for index 4. Index 4 equals len(nums), so the base case returns 0. Now the answers come back. Index 3 returns 9 + 0 = 9. Index 2 returns 7 + 9 = 16. Index 1 returns 5 + 16 = 21. Index 0 returns 3 + 21 = 24.

Recursion depth and RecursionError

Each recursive call uses a frame, and Python limits how many frames can be on the stack at once. The limit is called the recursion limit. You can read it with sys.getrecursionlimit(). On the Python 3.14 install used to test this lesson, the limit is 1000.

Forgetting the base case makes a recursive function run past that limit. The function below has no base case, so it never stops calling itself:

Output:

1000
RecursionError: maximum recursion depth exceeded
program still running

The try block holds the code that might fail, and the except block holds the code that runs when it fails. Python raises a RecursionError when the limit is reached. The except block catches it, so the program can print a message and keep going. In normal code you should not depend on this. The fix is to add a base case, or to rewrite the function as a loop.

Without the try block, the same function ends the program with a traceback:

def forever(n):
    return forever(n + 1) + 1
 
forever(1)

Output, with the first part of each File line replaced by ...:

Traceback (most recent call last):
  File ".../t05_limit_uncaught.py", line 4, in <module>
    forever(1)
    ~~~~~~~^^^
  File ".../t05_limit_uncaught.py", line 2, in forever
    return forever(n + 1) + 1
           ~~~~~~~^^^^^^^
  File ".../t05_limit_uncaught.py", line 2, in forever
    return forever(n + 1) + 1
           ~~~~~~~^^^^^^^
  File ".../t05_limit_uncaught.py", line 2, in forever
    return forever(n + 1) + 1
           ~~~~~~~^^^^^^^
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

The traceback shows the same line many times, because each frame runs the same line. Python prints [Previous line repeated 996 more times] to save space. The last line is the error to recognise.

Python does not remove a frame early, even when a call is the last step of a function. So a recursion that is 5000 steps deep needs 5000 frames, and it fails here. For long, straight-line work, use a loop. A loop uses one frame however many times it runs.

Every recursive function needs three things: a base case that does not call itself, a step that moves toward the base case, and a guarantee that the step makes progress. The factorial function has all three. The n - 1 moves toward 1, and the n <= 1 test stops it. A function that calls factorial(n + 1) moves the wrong way and fails with a RecursionError.

Reading a traceback

A traceback is Python's record of the call stack at the moment of an error. Here is a program where an error happens three calls deep:

def b(n):
    return 10 // n
 
def a(n):
    return b(n - 1)
 
def main():
    print(a(1))
 
main()

Output, with the first part of each File line replaced by ...:

Traceback (most recent call last):
  File ".../t02_traceback.py", line 10, in <module>
    main()
    ~~~~^^
  File ".../t02_traceback.py", line 8, in main
    print(a(1))
          ~^^^
  File ".../t02_traceback.py", line 5, in a
    return b(n - 1)
  File ".../t02_traceback.py", line 2, in b
    return 10 // n
           ~~~^^~~
ZeroDivisionError: division by zero

Read the traceback from the bottom up when you want the place where the error happened. The last File entry is the innermost frame, which is b. Above it are a, then main, then the top-level code. Each entry shows the line that was running in that frame. The final line gives the error type and message, ZeroDivisionError: division by zero.

The File lines show the folder on your machine, and the line numbers follow your file.

Countdown and indirect recursion

A recursive function can print on the way down and on the way up. This shows the two phases directly:

Output:

enter 2
enter 1
enter 0
base case
leave 1
leave 2

The enter lines come on the way down, as each frame is pushed. The leave lines come on the way up, as each frame returns. The leave line for n runs only after the call for n - 1 has finished.

Recursion does not have to be one function calling itself. Two functions can call each other in a cycle. This is called indirect recursion. The stack behaves the same way. The chain ends only if one of the functions reaches a base case.

Output:

False
True
True

Trace is_even(3). It calls is_odd(2), which calls is_even(1), which calls is_odd(0). That call hits its base case and returns False. The answer comes back up the chain, and is_even(3) returns False, which is correct, because 3 is odd. If either base case were missing, the cycle would fail with a RecursionError, just as a single function without a base case does.

Pass by object: why a swap does not swap

Now the second surprise. Here is a function that tries to swap two numbers:

Output:

inside: 2 1
outside: 1 2

Inside swap, the names a and b are exchanged, and the first line shows the swapped values. Outside, x and y are unchanged. Python does not copy the number when you call the function. The parameter a becomes a second name for the same object that x points to. The parameter b becomes a second name for the object that y points to. Then a, b = b, a makes a and b point at different objects. It does not change x or y, because those names were never reassigned.

Java programmers often call this pass by value, because Java copies each argument. Python's rule is different in wording but the result is the same here: the function receives the object, and it cannot rebind the caller's names. The next two sections show when the function can change the object itself, which is where the difference from a copy matters.

To get the swapped values back, return them. Python returns several values as a tuple, and the caller unpacks them into two names:

Output:

after returning: 2 1

The expression x, y = swap(x, y) assigns the returned values back to x and y. The function does not need to change the caller's names. The caller does the assignment.

Immutable and mutable values

Whether a function can change the caller's value depends on the type of the object. Some objects cannot be changed after they are made. These are immutable values, and they include integers, floats, strings, booleans and tuples. Other objects can be changed in place. These are mutable values, and they include lists, dictionaries and sets.

Output:

True
[1, 2, 3]
[1, 2, 3] [1, 2, 3, 4]
False
abc ABC
5 6
False

The operator is checks whether two names point to the same object. After b = a, both names point to one list, so b.append(3) changes what a sees. a.copy() makes a new list with the same items. Changing c does not change a.

A string cannot be changed in place. s.upper() returns a new string, and s still holds abc. A number works the same way. m += 1 makes m point to a new integer, 6. n still points to 5. The check n is m gives False, because they are now different objects.

The rule is short: a function that changes an immutable value must return the new value. A function that changes a mutable value, such as a list, changes the object the caller also sees.

Changing a list in a function

A list is mutable, so a function can change its contents, and the caller sees the change. A function can also assign a new list to its parameter name, and the caller does not see that.

Output:

[10, 6]
inside replace: [0, 0]
[10, 6]

double_first writes into the list that nums points to, so the caller's list now starts with 10. replace creates a new list and gives the name items that new list. The name items is gone when the function returns. The caller's nums still points at the original list.

A function that wants to keep the caller's list unchanged can make its own copy first. sorted is a built-in function that returns a new sorted list, and it leaves the input alone:

Output:

[1, 2, 3]
[3, 1, 2]
None
[1, 2, 3]

original.sort() is different. It sorts the list in place, and it returns None. If you write result = original.sort(), the name result gets None, not the sorted list. Use sorted(original) when you want a new list, and original.sort() when you want to change the list you have.

Returning new values

The rule for numbers is simple: to change a value, return it, and let the caller assign it. The caller writes x = increment(x) to store the new value. Here is a short example that shows the wrong way and the right way:

Output:

5
6

increment_wrong rebinds its own name n and then ends, so the change is lost. increment_right returns the new value, and the caller stores it. The difference is where the new value goes. A return sends it back. An assignment inside the function ends with the function.

Common mistakes

Writing a swap function for two numbers and expecting the caller's variables to change. They do not, because the function can only rebind its own names. Return both values and assign them in the caller.

Expecting a function to change a number or a string argument in place. Numbers and strings cannot be changed in place. Return the new value and assign it.

Thinking that reassigning a list parameter changes the caller's list. Reassigning the parameter only changes the function's name. Changing items with items[0] = ... or with a method such as append does change the caller's list.

Assigning the result of list.sort() to a name and getting None. sort changes the list and returns None. Use sorted to get a new list.

Forgetting return. A function without a return gives None. The code below runs without an error, and the result is None:

Output:

None

Recursion without a base case, which ends in RecursionError: maximum recursion depth exceeded. Check that every recursive path reaches a return that does not call the function again.

Debugging a wrong result step by step

Suppose a program prints outside: 2 1 when you expected 1 2. Start by asking which name the function changed. If the function changed a parameter name, the caller's name is unaffected, so look at what the caller prints. If the function changed an item in a list, the caller will see it, so look for an unexpected change to a list.

Next, trace the stack. Write the frames on paper: the top-level code at the bottom, then each call as it happens. For each frame, write its parameters and locals, and the values they hold at that moment. Then follow each value into and out of each frame. Most confusion about arguments disappears once you see which names point to which objects.

For a recursive function that gives a wrong answer, trace the smallest call first. Check the base case by hand. Then trace one call up, and check that its combining step uses the value that came back. A wrong base case or a wrong combining step is almost always the cause.

Variations and edge cases

Deep recursion uses many frames, and each frame costs memory. The recursion limit is a safety stop, not a size you should aim for. For problems that can go many thousands of steps deep, use a loop, or make the recursion shallower by halving the problem each time.

Recursion can be rewritten as a loop, and a loop can be rewritten as recursion. Choose the shape that is easier to read. Recursion matches tree-shaped problems well. A loop is safer for long, straight-line work, because it uses one frame however long it runs.

A function can return a list, a tuple or a dictionary, which lets it hand back several results at once. The caller then holds a reference to the object the function made. This is a common way around the one-return limit.

Some recursive functions call themselves twice, such as the Fibonacci function. The stack then holds a tree of frames, and the same answer can be computed many times. Dynamic programming, in a later module, fixes this by remembering answers.

Interview-style questions

An interviewer may ask, "Does Python pass arguments by value or by reference?" A careful answer is that Python passes the object itself. The parameter becomes another name for it. A function can change a mutable object that the caller also sees, but it cannot make the caller's name point at a different object.

They might ask, "Why does this swap function not work?" The answer is that the function can only rebind its own names. A function that swaps two values must return both, or work on a list or object that the caller can also see.

A third question is, "What is a stack overflow, and how do you prevent it?" In Python this is a RecursionError. Describe the frames piling up without a base case, and name the base case as the fix. Mention that a loop can replace recursion when the depth is large.

A fourth question is, "Trace the stack for factorial(4)." Write the four frames going down and the four values coming back up: 1, 2, 6 and 24. This is a common whiteboard task, and a clear trace earns most of the marks.

Real-world uses

Every program that calls functions depends on the call stack. When a web server handles a request, the request passes through layers of functions, and each layer is a frame. When a Python program crashes with a traceback, the traceback lists the frames, and reading it from the bottom up tells you which call failed.

Argument passing explains why library functions often return new values instead of changing the input. sorted returns a new list and leaves the original alone, while list.sort changes the list it is called on. Knowing which of the two a function does tells you what the caller will see afterwards.

Recursion is used in walking folder trees, in parsing nested data such as JSON, and in many search algorithms. Each of these depends on a clear base case. A recursive parser that forgets its base case fails with the same RecursionError you met here.

Practice

1. Trace the stack for a program where the top-level code calls a, a calls b, and b calls c. Write the stack at the deepest moment, when c is running.

Show the answer

From the top: c, b, a, then the top-level code. Four frames are on the stack, and c is the only one doing work.

2. Write increment(n) that returns n + 1, and use it as x = increment(x) with x = 4. Print the result.

Show the answer

The output is 5.

3. Write a function reverse_in_place(items) that reverses a list by swapping items from both ends toward the middle. Check that the caller sees the change with the list [1, 2, 3].

Show the answer

The output is [3, 2, 1]. The function changes the list it was given, so the caller's list is reversed too. The function returns nothing.

4. Trace factorial(4) by listing the value each frame returns as the stack unwinds. Then check your answer by running it.

Show the answer

The frames return 1 for factorial(1), then 2, then 6, then 24. The output is 24.

5. Explain why a function set_zero(n) that does n = 0 leaves the caller's number unchanged. Say what the parameter n is at the start of the call, and what the assignment changes.

Show the answer

At the start of the call, n is another name for the same integer the caller passed. The assignment n = 0 makes n point at the integer 0. It does not change the integer the caller holds, and the caller's name still points at the original number.

6. Write a recursive function countdown(n) that prints n, then calls itself with n - 1, until n is 0. At 0, print liftoff and return. Call it with 3 and predict the output.

Show the answer

The output is 3, 2, 1, then liftoff, one per line. The base case is n == 0, which prints liftoff and returns without calling the function again.

7. A function bad(n) returns bad(n - 1) + 1 and has no base case. What happens when you call it? Write a version that returns 0 when n is 0 or less, and call it with 4.

Show the answer

Each call adds a frame and never returns, so Python raises RecursionError: maximum recursion depth exceeded. This version stops:

The output is 4.

8. Write a recursive function factorial(n) and print factorial(6). Predict the output first.

Show the answer

The output is 720.

9. A function fill(items) sets every item of the list to 7 with a loop. Call it on [0, 0, 0] from the top-level code and print the list. Predict the output.

Show the answer

The output is [7, 7, 7]. The function changes the list object that the caller passed, so the caller sees the change.

10. Explain why def use_new(items): items = [9] does not change the caller's list, while def change(items): items[0] = 9 does.

Show the answer

The first function gives its own name items a new list. The caller's name still points at the original list, so the caller sees no change. The second function uses the name to reach the list that the caller also holds, and it changes an item in that list. The caller sees the change.

11. Write a function largest(items) that returns the largest number in a list. Test it with [3, 9, 2, 9, 7] and predict the result.

Show the answer

The output is 9. The function starts with the first item as best, then compares each remaining item with it.

12. Explain in plain words what a frame contains, and why two recursive calls can both have a local called n without any clash.

Show the answer

A frame holds one call's parameters, its local names, and the place to continue in the caller. Each call gets its own frame, so each n lives in a separate frame. No call can see another call's n.

What you now know

• The call stack is a stack of frames, one per active call. The frame on top is the function that is running, and a frame is removed when its function returns.
• A frame holds the parameters, the local names and the return point of one call.
• Recursion pushes a frame for each level on the way down, then returns the answers on the way up.
• A recursive function without a base case runs past the recursion limit and raises RecursionError. On this install the limit is 1000.
• A traceback lists the frames at the moment of an error. Read it from the bottom up to find the innermost call.
• Python passes the object itself. A parameter is another name for it. Reassigning the parameter does not change the caller's name, but changing a mutable object does change what the caller sees.
• Numbers, strings and tuples cannot be changed in place. To change one, return the new value and assign it.