Recursion: Functions Calling Themselves
Nested function calls occur when one function invokes another during its execution, causing the first function to pause while the second runs.
Try it: The Call Stack
How the call stack keeps track of function calls: each call pushes a frame with its own arguments and local variables, and each return pops it.
How it works
- Calling a function pushes a new frame on top of the stack; the caller pauses.
- The frame holds that call's parameters and local variables.
- When the function returns, its frame is popped and the return value goes back to the paused caller.
- A recursive function pushes one frame per call until the base case, then the frames unwind in reverse order.
Default run (17 steps): Program starts: main is about to call factorial(4). … The stack is empty again. Result: 24. Deepest point: 4 frames, 4 calls in total.
Loading the simulation…
The Pause Inside a Call
A function does not always run from its first line to its last line without interruption. During its execution, it may call another function. When that happens, the current function pauses while the called function runs. After the called function finishes, Python returns to the paused function and continues from the exact location where the call occurred.
Imagine a conversation in which one person asks another person a question. The second person must ask a third person before answering. The first person waits, the second person waits, and the third person answers first. The second person then answers the first person, and the first person can continue. Nested function calls follow the same layered pattern.
What do you think happens?
Suppose function_a calls function_b, and function_b calls function_c. Which function gets to finish first?
Reveal answer
function_c
function_a pauses while function_b runs, and function_b pauses while function_c runs. The innermost active call finishes first. Control then returns to function_b, and later to function_a.
Growing the Call Stack
Python uses a call stack to track active functions and their execution order. Every time a function is called, Python adds a frame for that call to the top of the stack. A frame represents an active function invocation and the information Python needs to continue it later. Every time a function returns, Python removes the top frame. The most recently called function must return before execution can move back to the function beneath it.
The stack grows downward into the call chain as new functions begin. In the source scenario, main calls greet_user, greet_user calls get_name, and get_name calls ask_question. At the deepest point, all four functions are active. ask_question is running, while get_name and greet_user are paused and waiting for their called functions to finish.
Following Control Through Layers
Tracing Three Nested Calls
Trace the execution when main calls function_a, function_a calls function_b, and function_b calls function_c.
- 11. Start in main
main begins executing and reaches its call to function_a.
- 22. Enter function_a
function_a is added to the call stack. main pauses while function_a runs.
- 33. Enter function_b
function_a reaches its call to function_b. function_a pauses, and function_b is added above it.
- 44. Enter function_c
function_b reaches its call to function_c. function_b pauses, and function_c becomes the active top frame.
- 55. Return from function_c
function_c finishes and is removed from the stack. function_b resumes at the point immediately after its call to function_c.
- 66. Return from function_b
function_b finishes and is removed. function_a resumes at the point immediately after its call to function_b.
- 77. Return from function_a
function_a finishes and is removed. main resumes at the point immediately after its call to function_a.
The call order is main, function_a, function_b, function_c. The return order is function_c, function_b, function_a, and then main continues.
A useful tracing habit is to separate calls from returns. Calls move control deeper into the chain and add frames. Returns move control back toward the caller and remove frames. Execution cannot return to a function that has not yet been called, and it cannot skip over the most recently active function.
Resuming at the Paused Line
When a called function completes, Python does not restart the calling function from the beginning. It resumes at the exact line where the call occurred, preserving the calling function's state. The caller may then use the returned value, continue with its next operation, or reach the end of its body.
Each active function also has its own local scope. Its local variables exist while that function is on the call stack. When the function returns and its frame is removed, those local variables are destroyed. A later call to the same function receives a fresh set of local variables rather than reusing the earlier call's local scope.
Recursion and Repeated Frames
Recursion is the case where a function calls itself during its own execution. The self-call is still a function call, so Python adds another active frame to the call stack before the earlier invocation has returned. The earlier invocation pauses while the newer invocation runs. When the newer invocation returns, Python resumes the earlier invocation at the point where the self-call occurred.
The important point is that the earlier invocation does not disappear when it makes the self-call. It remains active and paused on the call stack. Each invocation has its own frame and its own local scope. Because every active invocation must eventually return for the stack to shrink, uncontrolled self-calls can lead to infinite recursion, one of the mistakes that call-stack knowledge helps you recognize.
Mistakes in Stack Tracing
Common mistake Assuming the caller keeps running while the called function runs.
What it looks likeTreating greet_user as active work while get_name is executing.
Why it failsThe calling function pauses while the called function runs. It remains on the stack, but it is waiting rather than continuing past the call.
Do this insteadMark the caller as paused and follow the newly called function at the top of the stack.
Common mistake Returning directly to an older function.
What it looks likeMoving from ask_question straight back to main while get_name is still active.
Why it failsReturns remove only the top frame. The most recently called function must return to its immediate caller first.
Do this insteadTrace returns in reverse call order: ask_question to get_name, get_name to greet_user, and then greet_user to main.
Common mistake Starting the caller over after a return.
What it looks likeRestarting greet_user from its first line after get_name completes.
Why it failsPython resumes at the exact line where the call occurred and preserves the caller's state.
Do this insteadContinue with the line immediately after the completed call.
Common mistake Expecting one function's local variables to remain available outside that function.
What it looks likeTrying to use a local variable from function_b after function_b has returned.
Why it failsA function's local variables exist only while that function is on the call stack and are destroyed when it returns.
Do this insteadUse values returned by the function rather than assuming its local variables remain accessible.
Common mistake Ignoring uncontrolled recursion.
What it looks likeAllowing a function to keep calling itself without reaching a point at which calls finish.
Why it failsEach self-call adds another active frame, so the call stack continues growing instead of shrinking.
Do this insteadWhen tracing recursive behavior, check how and when the active invocations return.
When debugging nested or recursive behavior, write the active functions in call order and cross them off in return order. If an error occurs, Python's traceback provides a printout of the call stack at that moment, showing which functions were active and the order in which they were called.
Trace It Yourself
A program begins in main. main calls prepare, prepare calls validate, and validate calls check. Trace the complete call order, identify which functions are paused while check runs, and then trace the complete return order.
Hints
- Add a function to the call stack whenever it is called.
- The top function is the one currently running.
- Remove functions from the top in reverse order when they return.
Practice Solution
Trace main calling prepare, prepare calling validate, and validate calling check.
- 1Call order
The functions become active in this order: main, prepare, validate, and check.
- 2Paused functions
While check runs, validate, prepare, and main remain active but paused.
- 3Return order
The functions finish in reverse order: check returns to validate, validate returns to prepare, and prepare returns to main.
The stack grows as main, prepare, validate, and check are added, then shrinks as check, validate, and prepare return.
What to Remember
- 1A nested call pauses the current function while the called function runs.
- 2Each function call adds a frame to the call stack, and each return removes the top frame.
- 3Python resumes the caller at the exact point where the called function completed.
- 4Calls move deeper into the stack; returns unwind the stack in reverse order.
- 5Recursion adds another active invocation of the same function, so earlier invocations remain paused on the stack.
At a glance
- Nested function calls create a chain in which each caller pauses while its called function runs.
- The call stack records active functions, their order, and where paused execution must resume.
- The most recently called function returns first, producing last-in-first-out execution.
- Recursion is a self-call that adds another active frame before the earlier invocation finishes.
- Local variables belong to their active function call and are destroyed when that call returns.