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.
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
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.
1. Start in main: main begins executing and reaches its call to function_a.
2. Enter function_a: function_a is added to the call stack. main pauses while function_a runs.
3. Enter function_b: function_a reaches its call to function_b. function_a pauses, and function_b is added above it.
4. Enter function_c: function_b reaches its call to function_c. function_b pauses, and function_c becomes the active top frame.
5. 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.
6. Return from function_b: function_b finishes and is removed. function_a resumes at the point immediately after its call to function_b.
7. 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
Assuming the caller keeps running while the called function runs.
The calling function pauses while the called function runs. It remains on the stack, but it is waiting rather than continuing past the call.
Fix:
Mark the caller as paused and follow the newly called function at the top of the stack.Returning directly to an older function.
Returns remove only the top frame. The most recently called function must return to its immediate caller first.
Fix:
Trace returns in reverse call order: ask_question to get_name, get_name to greet_user, and then greet_user to main.Starting the caller over after a return.
Python resumes at the exact line where the call occurred and preserves the caller's state.
Fix:
Continue with the line immediately after the completed call.Expecting one function's local variables to remain available outside that function.
A function's local variables exist only while that function is on the call stack and are destroyed when it returns.
Fix:
Use values returned by the function rather than assuming its local variables remain accessible.Ignoring uncontrolled recursion.
Each self-call adds another active frame, so the call stack continues growing instead of shrinking.
Fix:
When 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.
Call order: The functions become active in this order: main, prepare, validate, and check.
Paused functions: While check runs, validate, prepare, and main remain active but paused.
Return 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
- A nested call pauses the current function while the called function runs.
- Each function call adds a frame to the call stack, and each return removes the top frame.
- Python resumes the caller at the exact point where the called function completed.
- Calls move deeper into the stack; returns unwind the stack in reverse order.
- Recursion adds another active invocation of the same function, so earlier invocations remain paused on the stack.
Key Takeaways
- 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.