In this video, we're going to trace through

a series of recursive calls to the function Fibonacci.

Recall that Fibonacci is defined for any value n as

the sum of Fibonacci of n minus 1 and Fibonacci of n minus 2.

If we begin with the Fibonacci of five,

we're going to see two recursive calls for n minus 1 and n minus two.

And this will occur repeatedly until we hit a leaf node.

A leaf node is, Fibonacci of zero or Fibonacci of one,

which simply have the definition zero and one respectively.

At the end of these series of calls,

you can see that we've called Fibonacci many times.

Specifically, we've called Fibonacci of zero,

three times, Fibonacci of one,

five times, Fibonacci of two,

three times, and we've called Fibonacci of three, twice.

So, although this recursive definition is correct,

it's not particularly efficient.

The problem is not that recursion is slow,

it's that algorithms that recompute the same thing many times are slow.

Whether or not this is acceptable depends on your programming context,

where you should be aware of how a problem like this can affect performance.

If slow performance were unacceptable,

you could rethink your algorithm to avoid repeating

calculations or you could use memoization.

Keeping a table of values that have already been computed,

and check that table to see if the answer has

already been computed before doing it again.