Recursion: a function that calls itself
Work out factorials with a function that calls itself. Watch the call stack grow one frame for every call down to the base case, then shrink as each call returns its answer, and see why a recursive function needs a base case.
Core concept
A recursive function solves a problem by calling itself on a smaller version of it; a base case answers the smallest version directly, so the calls stop and the answers come back up the call stack
Topic: Functions and recursion
The factorial of a number, written n!, is the product of all the whole numbers from n down to 1: 4! = 4 × 3 × 2 × 1 = 24. Notice that 4! is just 4 × 3!, and 3! is 3 × 2!. A function can use that idea and call itself: fact(n) returns n × fact(n − 1). This is called recursion. Each call waits for a smaller call to answer, so the calls pile up on the call stack, newest on top. They must stop somewhere: the base case, IF n <= 1 THEN RETURN 1, answers the smallest problem straight away without calling again. Then the answers come back down the pile: fact(1) gives 1, fact(2) gives 2 × 1, fact(3) gives 3 × 2, until the first call has its answer.
What you will learn
- Explain what a recursive function and a base case are.
- Trace the call stack as recursive calls grow and return.
- Predict the value a recursive function returns.
- Explain what goes wrong without a base case.
Before you start
- Know how a function takes a parameter and returns a value.
Materials
- A notebook to draw the call stack
Equipment
- None
Procedure
- Run fact(4) and read the answer, the number of calls and the deepest stack.
- Step through it and watch each frame appear and then return.
- Try number = 6, then number = 1 (the base case at once).
- Answer the practice challenges.