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!