Recursive Functions

A **function **that calls itself within its own definition
Used to solve problems that can be **broken **down into smaller subproblems
Must have two cases:
- Base case to **stop **the **recursion **and avoid infinite loops
- Recursive case that **reduces **the **problem **and calls the function again

Advantages

Simplifies code and algorithm design, especially for recursive algorithms
Reduces complexity by breaking down problems into subproblems
**Cleaner **and **shorter code **

Disadvantages

**Higher memory usage **as each recursive call adds a new stack frame to the call stack, consuming more memory
**Risk **of **stack overflow **since infinite recursion can exceed the stack limit, causing the program to crash
**Slower execution **as the function values can be calculated again many times
**Harder **to debug

Comparison with Iterative Functions

Convergence

Iterative solution is a loop which converges to a solution
Recursive solution is a procedure which keeps calling itself until a solution is found

Local Variables

Iterative solution have successive values of its local variables are overwritten
Recursive solution have successive values of its local variables are all preserved

Trace Diagram for Recursive Functions

How the Call Stack works

1. Function Call

Function is called

Python Virtual Machine (PVM) allocates a stack frame on the call stack
This frame stores:
- **Arguments **passed to the function

Return address (the next instruction to execute after the function finishes)

**Memory **for the return value

2. Stack Frame Created

Each stack frame is a “box” of local context for that particular function call:
- Local variables

Function parameters

Intermediate data

3. Execution of Function

The function **executes **using the data in its stack frame

4. Function Returns

When the function completes:
- The return value is passed back to the caller
- The return address is used to jump back to where the function is called
- The function’s stack frame is popped off (removed) from the call stack

5. Back to Caller

Execution continues from where the function was called