## Efficiency

If we're not careful, making multiple recursive calls can lead to exponential running times real fast. Luckily, with a little thought, we can often avoid programs that unnecessarily repeat tremendous amounts of work.

Consider this natural implementation of the `fib` function:

``````fun fib (n: int) =
if n < 1 then
0
else if n = 1 then
1
else
fib (n - 1) + fib (n - 2)``````

How many times will `fib n` recurse? Let's call this number `F(n)`.

Well, if `n < 2`, then `fib` doesn't recurse, so `F(n) = 0`.

What about `n >= 2`? In this case, `fib n` makes two recursive calls, `fib (n - 1)` and `fib (n - 2)`, which make `F(n - 2)` and `F(n - 1)` recursive calls respectively. So in total, `F(n) = 2 + F(n - 1) + F(n - 2)`.

`n` `F(n)` graph
0 0
1 0
2 2 **
3 4 ****
4 8 ********
5 14 **************
6 24 ************************
7 40 ****************************************
8 66 ******************************************************************
9 108 ************************************************************************************************************

That grows pretty fast... it looks exponential in fact. Basically, it's a non-starter.

But we can do better!

Consider this alternate implementation of `fib`:

``````fun fib' (n: int) =
let
fun loop (i: int, f0: int, f1: int) =
if i = n then
f0
else
loop (i+1, f0 + f1, f0)
in
if n < 1 then
0
else
loop (1, 1, 0)
end``````

Using the `loop` helper function, `fib' n` only makes `n` recursive calls. Yay!