> For the complete documentation index, see [llms.txt](https://catherine-leung.gitbook.io/data-strutures-and-algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://catherine-leung.gitbook.io/data-strutures-and-algorithms/recursion/how-do-recursive-functions-work.md).
# How do recursive functions work?
To understand how recursion works, we need to look at the behaviour of the run time stack as we make the function calls.
{% hint style="info" %}
The runtime stack is a structure that keeps track of function calls and local variables as the program runs. When a program begins, the main() function is placed on the run time stack along with all variables local to main(). Each time a function is called, it gets added to the top of the runtime stack along with variables and parameters local to that function. Variables below it become inaccessible. When a function returns, the function along with it's local variables are popped off the stack allowing access to its caller and its callers variables.
{% endhint %}
Suppose we have the following program:
```cpp
unsigned int factorial(unsigned int n){
unsigned int rc = 1 ; //base case result
if(n > 1) //if n > 1 we have the recursive case
rc= n * factorial(n-1); //rc is n * (n-1)!
}
return rc;
}
int main(void){
unsigned int x = factorial(4);
return 0;
}
```
Lets trace what happens to it with respect to the run time stack:
Program begins, main() function is placed on stack along with local variable x. 
factorial(4) is called, so we push factorial(4) onto the stack along with local variables n and rc.
n is 4, and thus the if statement in line 3 is true, thus we need to call factorial(3) to complete line 4. 
{% hint style="info" %}
Note that in each function call to factorial on stack there is a value for n and rc. Each n and rc are separate variables so changing it in one function call on stack will have no effect on values held in other factorial function calls on stack.
{% endhint %}
Now, the n is 3 which makes the if statement true. Thus, we make a call to factorial(2). 
Once again, the if statement is true, and thus, we need to call factorial(1). 
Once we make this call though, our if statment is false. Thus, we return rc popping the stack 
Once it is returned we can complete our calculation for rc = 2. This is returned, popping the stack 
Once it is returned we can complete our calculation for rc = 6. This is returned, popping the stack 
Once it is returned we can complete our calculation for rc = 24. This is returned, popping the stack 
---
# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.
## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:
```
GET https://catherine-leung.gitbook.io/data-strutures-and-algorithms/recursion/how-do-recursive-functions-work.md?ask=&goal=
```
`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.