Question

Os números de Fibonacci constituem uma seqüênciade números na qual os dois primeiros elementos são 0 e 1e os demais, a soma dos dois elementos imediatamenteanteriores na seqüência. Como exemplo, a seqüênciaformada pelos 10 primeiros números de Fibonacci é: 0, 1,1, 2, 3, 5, 8, 13, 21, 34. Mais precisamente, é possíveldefinir os números de Fibonacci pela seguinte relação derecorrência:fib (n) = 0, se n = 0fib (n) = 1, se n = 1fib (n) = fib (n - 1) + fib (n - 2), se n > 1Abaixo, apresenta-se uma implementação emlinguagem funcional para essa relação de recorrência:fib :: Integer -> Integerfib 0 = 0fib 1 = 1fib n = fib (n - 1) + fib (n - 2)Considerando que o programa acima não reutilizeresultados previamente computados, quantas chamadassão feitas à função fib para computar fib 5?A 11B 12C 15D 24E 25

#ENADE

Answer 1

A alternativa correta é: C) 15

Se realizam quinze chamadas. Para solucionar o exercício acima de maneira mais prática, pode-se realizar a construção de uma abordagem chamada árvore de chamadas de função fib, gerada através da recursão sobre a função fib (em anexo), logo após, deve-se realizar a contagem dos nós (ou chamadas de função), nesse caso, o argumento 5 (computar fib 5), serão realizadas quinze chamadas à função fib para computar fib 5.

Espero ter ajudado!