Concursos públicos

Os números de Fibonacci constituem uma seqüência de números na qual os dois primeiros elementos são 0 e 1 e os demais, a soma dos dois elementos imediatamente anteriores na seqüência. Como exemplo, a seqüência formada pelos 10 primeiros números de Fibonacci é: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34. Mais precisamente, é possível definir os números de Fibonacci pela seguinte relação de recorrência:

fib (n) = 0, se n = 0

fib (n) = 1, se n = 1

fib (n) = fib (n - 1) + fib (n - 2), se n gt; 1

Abaixo, apresenta-se uma implementação em linguagem funcional para essa relação de recorrência:

Considerando que o programa acima não reutilize resultados previamente computados, quantas chamadas são feitas à função fib para computar fib 5?