Projeto de pesquisa: aperfeiçoando a implementação de Fibonacci recursiva. Na Seção 5.15, o algoritmo recursivo que usamos para calcular números de Fibonacci foi intuitivamente atraente. Porém, lembre-se de que o algoritmo resultou na explosão exponencial das chamadas de função recursivas. Pesquise a implementação de Fibonacci recursiva on-line. Estude as diversas técnicas, incluindo a versão iterativa do Exercício 5.35 e as versões que usam apenas a chamada ‘recursão de cauda’ (tail recursion). Discuta os méritos relativos de cada uma.

Passo 1

Fala Galera!!! Tudo certo? Espero que sim!!! Bora para mais um exercício.

Nesse exercício vamos estudar alguns outros métodos utilizados para calcular os números de Fibonacci. Os métodos que iremos estudar será por recursividade, interação, recursão de calda.

A forma mais tradicional de calcular os números de Fibonacci é através de uma função recursiva, porém esse método acaba não sendo tão vantajoso, pois resulta em uma explosão exponencial das chamadas de funções recursiva. Um exemplo de uma função recursiva é:

int fibonacci( int num){

if(num ==0 || num ==1){

return num;

}

else{

return fibonacci ( num - 1 ) + fibonacci( num - 2 );

}

}

Passo 2

No método por interação o laço de repetição é controlado através do argumento da função. Um exemplo de uma função interativa para calcular os números de Fibonacci:

int fibonacci( int num){

int count = 0, fib1 = 0, fib2 = 0, fibNum;

for( count =0 ; count

if ( count

fibNum = count;

}

else{

fibNum = fib1 + fib2;

fib1 = fib2;

fib2 = fibNum;

}

}

}

Passo 3

A recursão de cauda é uma técnica de recursão que faz menos uso de memória durante o processo de empilhamento, o que a torna mais rápida que a recursão comum. Em uma recursão de cauda, não é necessário guardar a posição onde foi feita a chamada, visto que a chamada é a última operação realizada pela função. Um exemplo de uma função recursiva de cauda para calcular os números de Fibonacci:

int fibonacci( int num, int fib, int temp){

swicth(num){

case 0:

return fib;

default:

return fib( num - 1, fib + temp, fib );

}

}

Na abordagem recursiva de cauda, ​​o número de chamadas recursivas é 1 a menos que o número para o qual o equivalente de Fibonnaci deve ser encontrado.

Passo 4

Agora vamos listar algumas vantagens dos métodos apresentados.

Função recursiva:

1) é a mais fácil de implementar

2) resolve o problema através da implementação do conceito dos números de Fibonacci. Onde soma os dois últimos números de Fibonacci

Função Interativa:

1) a abordagem interativa limita os ciclos de loop ao número para o qual o equivalente de Fibonacci é calculado.

2) o uso de variáveis ​​locais limita o argumento a ser passado para a função, diminuindo assim a complexidade do programa.

Função recursiva de calda:

1) a abordagem recursiva da cauda limita o número de chamadas recursivas ao número para o qual o equivalente de Fibonacci deve ser calculado.

2) o uso de recursão facilita a compreensão e a implementação, mantendo alta eficiência.

E assim, finalizamos nosso exercício galera!!!! Até o próximo.

Resposta

Desenvolvimento acima.