Recursive algorithms: factorial and Fibonacci

Overview

Fibonacci sequence recursively and why the towers of Hanoi puzzle is naturally recursive.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   State the value of 5 factorial.

   Model answer

   The value of 5 factorial is 120. The product is 5 × 4 × 3 × 2 × 1.

2. 2

   Define the Fibonacci sequence recursively.

   Model answer

   The first two Fibonacci numbers are both 1. Every later term is the sum of the two terms before it.

3. 3

   List the first seven terms of the Fibonacci sequence starting from 1.

   Model answer

   The first seven terms are 1, 1, 2, 3, 5, 8 and 13. Each term after the second is the sum of the previous two.

4. 4

   Using base cases fib(1) = 1 and fib(2) = 1, how many calls in total does the simple recursive Fibonacci function make to evaluate fib(5)?

   Model answer

   Nine calls are made in total. The value returned is 5.

5. 5

   Why is the simple recursive Fibonacci function inefficient?

   Model answer

   The same subproblems are recalculated many times because the two branches overlap. The number of calls grows exponentially with n.

6. 6

   How can the repeated work in a recursive Fibonacci function be avoided?

   Model answer

   Results already calculated can be stored in an array and looked up when needed again. Memoisation is the name given to this technique.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.