Recursion
Recursion
- A recursive algorithm calls itself with a smaller version of the same problem.
- It needs a base case to stop, and a recursive case that shrinks the input.
- The compiler handles it with the call stack.
Base case and recursive case
FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
IF n = 0 OR n = 1 THEN
RETURN 1 // base case
ELSE
RETURN n * Factorial(n - 1) // recursive case
ENDIF
ENDFUNCTION
- The base case is small enough to solve directly — without it the recursion never stops.
- The recursive case reduces the input and calls itself.
- Recursion suits self-similar problems: trees, divide-and-conquer (binary search, merge sort).
Practice
Every recursive algorithm must have a base case because:
The base case is the condition that ends the chain of calls; without it the recursion runs forever.
Practice
What does Factorial(4) return?
4 × 3 × 2 × 1 = 24.
Practice
Recursion is a natural fit for:
Self-similar structures (trees, divide-and-conquer) suit recursion; a plain loop is cleaner for simple iteration.
Tracing and risks
Factorial(4)calls down toFactorial(1)=1, then unwinds:2*1=2,3*2=6,4*6=24.- Risks: a missing base case → infinite recursion → stack overflow; deep recursion uses lots of memory; repeating work is slow (naive Fibonacci is exponential — use a loop or memoisation).
Practice
What happens if a recursive function never reaches its base case?
Endless recursion keeps pushing stack frames until the call stack overflows and the program crashes.
What the compiler does
- Each call needs its own copy of its parameters and local variables, kept on the call stack.
- For each call the compiler pushes a stack frame holding the parameters, local variables, and the return address (where to resume in the caller).
- On return, the value is handed back and the frame is popped. This is the same mechanism as ordinary calls — there's no special "recursion mechanism", which is why deep recursion can overflow the stack.
Practice
A stack frame for a function call holds:
Each frame stores that call's parameters, locals and where to resume — so calls don't trample each other.
You've got it
Key idea
- recursion = base case (stops it) + recursive case (shrinks the input and calls itself)
- a missing base case → infinite recursion → stack overflow
- each call gets a stack frame (parameters, locals, return address) on the call stack
- suits self-similar / divide-and-conquer problems; a loop is cleaner otherwise