When learning recursion, many programmers eventually ask a deeper question:
What is actually happening underneath the programming language when functions call themselves?
Consider the classic Lua factorial example:
function fact(n)
if n == 0 then
return 1
else
return n * fact(n - 1)
end
end
At first, the focus is usually on understanding recursion itself.
However, a curious learner may eventually wonder:
- How does the computer remember all those function calls?
- Where are the intermediate values stored?
- Is there some hidden program tracking everything?
- Can programming languages work without stacks?
- Can stacks be disabled?
The answers lead into computer architecture, operating systems, interpreters, and language design.
The Hidden Structure: The Call Stack
Most programming languages use a structure called a call stack to keep track of active function calls.
The call stack stores information such as:
- Function parameters
- Local variables
- Return addresses
- Temporary values
The primary purpose of the call stack is to remember where execution should continue after a function finishes.
A simple function call:
greet()
creates a stack frame.
When the function returns:
return
the stack frame is removed.
What Is a Stack Frame?
Each function call receives its own stack frame.
A stack frame typically contains:
Function name
Parameters
Local variables
Return address
Temporary values
For example:
+------------------+
| greet() |
+------------------+
When the function completes, that frame is removed and execution returns to the caller.
What Happens During Recursion?
Suppose:
fact(3)
is executed.
The stack grows:
+------------------+
| fact(3) |
+------------------+
Then:
+------------------+
| fact(2) |
+------------------+
| fact(3) |
+------------------+
Then:
+------------------+
| fact(1) |
+------------------+
| fact(2) |
+------------------+
| fact(3) |
+------------------+
Then:
+------------------+
| fact(0) |
+------------------+
| fact(1) |
+------------------+
| fact(2) |
+------------------+
| fact(3) |
+------------------+
Once the base case is reached:
return 1
the stack begins to unwind.
Frames are removed one by one until the original function call finishes. This process is known as stack unwinding.
Who Actually Maintains the Stack?
Many beginners imagine that the programming language itself keeps track of everything.
In reality, several layers cooperate:
Lua / Python / C Program
↓
Language Runtime / Interpreter
↓
Operating System
↓
CPU
↓
RAM
The call stack ultimately resides in memory.
The language runtime uses it, the operating system allocates it, and the CPU helps manage it.
The CPU’s Role
Modern processors typically include a special register known as the:
Stack Pointer
The stack pointer tracks the current top of the stack.
Every time a function is called:
Push new stack frame
Every time a function returns:
Pop stack frame
This mechanism allows nested and recursive function calls to work efficiently.
Why Recursion Eventually Fails
The stack is not infinite.
Every recursive call consumes additional stack space.
For example:
function bad(n)
return bad(n - 1)
end
never reaches a stopping condition.
Eventually the stack fills up and a stack overflow occurs.
This is why recursive functions require a base case.
Do All Programming Languages Use Stacks?
Almost all mainstream programming languages rely on stacks in some form.
Examples include:
- Lua
- Python
- C
- C++
- Java
- JavaScript
- Go
- Rust
The details differ, but the underlying idea remains the same. Function calls require somewhere to store execution state.
Does C Use a Stack?
Yes.
Consider:
int fact(int n)
{
if (n == 0)
return 1;
return n * fact(n - 1);
}
Each call creates a new stack frame.
Because C exposes low-level details more directly than many languages, understanding stacks is especially important when learning C.
Does Python Use a Stack?
Yes.
Python uses a call stack and also imposes a recursion limit.
The interpreter provides:
import sys
print(sys.getrecursionlimit())
which returns the maximum recursion depth allowed by the interpreter. Python includes this safeguard to help prevent infinite recursion from crashing the interpreter stack.
The limit can be adjusted:
sys.setrecursionlimit(2000)
although this should be done carefully because deeper recursion increases stack usage.
Does Lua Use a Stack?
Yes.
Lua maintains internal stacks for function calls and the Lua API itself.
The official Lua reference manual discusses stack management and stack overflow protection through functions such as:
lua_checkstack()
used when interacting with Lua’s C API.
Lua also includes protections against excessive call depth and stack overflows.
Are There Languages Without Stacks?
This question has a surprising answer.
While some historical computer systems lacked dedicated hardware stack support, programmers and compiler writers still implemented stack-like behavior in software.
In practice, almost every modern language relies on some form of stack because function calls require storage for:
- Parameters
- Local variables
- Return addresses
- Execution state
Without such storage, ordinary function calls would be extremely difficult to implement.
Can Stacks Be Disabled?
Generally, no.
Stacks are fundamental to how function calls work.
What developers can often change is:
- Stack size
- Recursion depth limits
- Tail-call optimizations (in some languages)
- Memory allocation strategies
But the concept of storing execution state somewhere remains essential.
Recursion Versus Iteration
Recursive factorial:
function fact(n)
if n == 0 then
return 1
else
return n * fact(n - 1)
end
end
Iterative factorial:
function fact(n)
local result = 1
for i = 1, n do
result = result * i
end
return result
end
The iterative version usually uses a single stack frame.
The recursive version creates many stack frames.
For very large problems, iterative approaches often consume less stack memory.
Key Takeaway
When a programmer writes:
fact(5)
the call is not handled solely by Lua.
A sophisticated chain of systems works together:
Lua Code
↓
Lua Interpreter
↓
Operating System
↓
CPU Stack Pointer
↓
Stack Frames in RAM
Understanding recursion often provides a first glimpse beneath a programming language and into the architecture of computers themselves. What initially appears to be a simple function call is actually supported by decades of innovations in programming language design, operating systems, compiler theory, and computer hardware.
Further Reading
Computer Science Concepts
Advanced Topics
- Tail Call Optimization
- Stack Overflow Errors
- Compiler Design
- Assembly Language Programming
- Operating System Process Memory Layout
- Virtual Machines and Interpreters
