More recursion, and its cost

What you will be able to do

After this lesson you can

• write recursive functions for sums, powers, digits and Fibonacci numbers,
• find the base case and the smaller problem for each,
• explain why the simple Fibonacci is slow, and
• choose between a loop and recursion.

Many problems fit

In each case, the problem gets smaller by one step: one less, one less exponent, one less digit.

The Fibonacci numbers

$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, \ldots$ Each number is the sum of the two before it. In code, that is exactly the definition: fibonacci(n) is fibonacci(n - 1) + fibonacci(n - 2). The function calls itself twice. This is short and beautiful. But there is a cost.

Predict first. How many calls does fibonacci(20) make? A few dozen? A few thousand? More?

The counts are 15, 177, 1973 and 21 891. For each step of 5 in n, the calls grow about eleven times. Why? Look at fibonacci(5). It needs fibonacci(4) and fibonacci(3). But fibonacci(4) also needs fibonacci(3). So fibonacci(3) is worked out twice, and fibonacci(2) three times, and so on. The same small values are worked out again and again. For fibonacci(50), the simple function would take hours.

The loop version at the end does the same job in n steps. fib_loop(50) is instant. The idea of the loop: keep the last two numbers, and move along.

In the next course, the workshop, you will see a way to keep the beauty of the recursive function and the speed of the loop: a memory in a dictionary.

Each step of n multiplies the calls by about 1.6. At n = 30 the simple version makes more than a million calls.

Loop or recursion?

Anything that can be done with recursion can be done with a loop, and the other way round. So which one?

A good rule: if the problem is naturally made of smaller copies of itself, recursion is clear. If you only repeat a step, use a loop. sum_to(n) is better as n * (n + 1) // 2 or a loop. A folder tree is better with recursion.

Common mistakes

• Using recursion for a simple repeat. A loop is shorter and safer.
• The simple Fibonacci for a big n. Far too slow.
• A base case that is not enough. fibonacci needs a base case for both 0 and 1: n < 2.
• A smaller problem that does not shrink. count_digits(n) calling itself with n // 1.
• Going too deep. A thousand calls is the limit.

Practice

Start with two quick questions. Each New numbers gives you a fresh one, so you can practise as long as you like.

Then the labs and the problems:

1. Warm-up. Open the problem A power by recursion and the problem Count the digits.
2. Build. Open the lab The Fibonacci numbers and the problem Why is the simple Fibonacci slow?
3. Stretch. Open the problem Loop or recursion? and choose for five jobs.

Remember these

• Many problems have a base case and a smaller problem.
• A simple recursive Fibonacci makes a huge number of calls, because it repeats the same work.
• A loop is often faster. Recursion is often clearer, for problems made of smaller copies.
• Anything recursive can be done with a loop.

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

1. What is fibonacci(6)? (The values are 0, 1, 1, 2, 3, 5, 8.)

2. Can every recursion be replaced by a loop?

3. Why does the simple Fibonacci work out the same value more than once?