Recursion and the Call Stack
Every recursive function needs a base case and progress toward it.
What is Recursion and the Call Stack?
Every recursive function needs a base case and progress toward it.
Solve a problem by reducing it to a smaller instance.
Important points
- Test empty, single-element, duplicate, and already sorted inputs.
- Separate correctness from optimization.
- Use the standard library in production unless a custom implementation is justified.
C and C++ code examples
main.c
#include <stdio.h>
unsigned long long factorial(unsigned number) {
return number < 2 ? 1 : number * factorial(number - 1);
}
int main(void) {
printf("%llu\n", factorial(6));
}
720C++
main.cpp
#include <iostream>
constexpr unsigned long long factorial(unsigned number) {
return number < 2 ? 1 : number * factorial(number - 1);
}
int main() {
constexpr auto value = factorial(6);
std::cout << value << '\n';
}
720C and C++ comparison
Each call consumes stack space, so the factorial versions use O(n) time and O(n) call-stack space. Large inputs need validation and often an iterative solution.
C
Loops, pointers, lengths, and temporary buffers are written explicitly.
C++
Iterators and standard algorithms separate operations from container representation.
Practice exercises
Run both versions, then modify them to observe the different language guarantees.
- Trace each comparison on paper.
- Test duplicates and extreme values.
- Benchmark the custom implementation against the standard library.