-
Galera, quem tiver dificuldade nesse exercício existe uma maneira fácil de se fazer, note que cada número, começando pelo 8 e decrementando terá duas chamadas, e estas, também terão duas chamadas (x(n-1) e x(n-2)), note que a chamada n<0 nunca será feita! É uma pegadinha ela estar ai! O algoritmo é um fibonacci recursivo. Montemos então uma arvore binária para a solução, começando por 8 e colocando x(n-1) a esquerda e x(n-2) a direita, a resposta ficará grande, mas repita o procedimento até encontrar 1(uns) e (zeros) e a arvore ficar completa, ao encontrar 1 e 0 você deve parar e seguir para o próximo ramo da árvore . Ao final, após montar a arvore você terá vários 1 e 0 nas folhas da árvore soma-los e encontrará o 21.
Note que o oitavo número da sequência fibonacci é exatamente o 21.
Parece complexo, mas quem está preparado faz esta questão em menos de 1 minuto.
-
Outra forma de resolver estas questões de funções recursivas é usando o princípio da fatoração:
x(0) = 0
x(1) = 1
x(2) = 1
x(3) = 2
x(4) = 3
x(5) = 5
x(6) = 8
x(7) = 13
x(8) = 21
-
Nessa função você teria que descer até o n = 2 para obter o valor de n = 1 e n = 0 e satisfazer as condições, uma observação é que não existiria iteração para n = 1 e n = 0, uma vez que haveria o retorno antes da recursão em de x(2).
x(8) = n = 7 + n = 6 = 13(vem do x(7)) + 8 (vem do x(6)) = 21
x(7) = n = 6 + n = 5 = 8 (vem do x(6)) + 5 (vem do x(5)) = 13
x(6) = n = 5 + n = 4 = 5 (vem do x(5)) + 3 (vem do x(4)) = 8
x(5) = n = 4 + n = 3 = 3 (vem do x(4)) + 2 (vem do x(3)) = 5
x(4) = n = 3 + n = 2 = 2 (vem do x(3)) + 1 (vem do x(2)) = 3
x(3) = n = 2 + n = 1 = 1 (vem do x(2)) + 1 (vem do if n==1 ret 1) = 2
x(2) = n = 1 + n = 0 = retorna 1 + 0 (if n==1 ret 1, if n==0 ret==0) = 1
-
Um outro pensamento para quem não identificou que se trata da sequência de Fibonacci:
0 1 1 2 3 5 8 13 21
Analisando o corpo da função:
1º quando n==0 return 0
2º quando n==1 return 1
3º pela função temos que: deve ser retornado x(n-1) + x(n-2)
4º recebemos como parâmetro: 8
Resolvendo:
n==2 = x(1) + x(0) = 1
n==3 = x(2) + x(1) = 2
n==4 = x(3) + x(2) = 3
n==5 = x(4) + x(3) = 5
n==6 = x(5) + x(4) = 8
n==7 = x(6) + x(5) = 13
por fim:
n==8 = x(7) + x(6) = 21
Demorararia um pouco mais para resolver dessa forma, mas vale fazer o teste de mesa se tiver um tempinho sobrando na prova e não souber analisando a questão. Bons estudos!
-
Força Guerreiro!!!!!!