07Functions
Recursion
A function that calls itself.
A function can call itself. This is called recursion. It suits problems that contain a smaller version of themselves. The factorial of n, written n!, is n × (n − 1) × ... × 1. So 5! is 5 × 4!, and 4! is 4 × 3!, and so on down to 1! = 1.
Expected output
၁
၂
၆
၂၄
၁၂၀
၇၂၀
Each recursive function needs two parts:
- A base case that gives the answer without calling itself:
n ≤ 1gives 1. - A recursive case that calls itself on a smaller problem: n − 1.
Each call works on a smaller n, so the calls reach the base case in the end and stop.
Two calls at once
The Fibonacci numbers start 0, 1, and each next number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, ... A recursive function can follow that rule word for word:
Expected output
၀
၁
၁
၂
၃
၅
၈
၁၃
၂၁
၃၄
၅၅
This version is simple to read but slow for large n, because it works out the same numbers again and again. The Fibonacci numbers program uses a loop instead.
Recursion without an end
If the base case is missing or never reached, the function calls itself forever. Zaka stops a program after 4096 calls that are still waiting to return:
Expected output
the program stopped: more than 4096 nested calls
Hands on
- Write a recursive function for the sum 1 + 2 + ... + n.
- Write a recursive function that counts the digits of a number (hint: n / 10 has one digit fewer).
Next: Pointers and the heap.