Problema: A sequência de Fibonacci é definida como:
Escreva uma função recursiva que retorne o n-ésimo termo da sequência de Fibonacci, sendo
dado.
Exemplo de entrada
Exemplo de saída
05 termo da sequencia de Fibonacci e 5.
06 termo da sequencia de Fibonacci e 8.
Exemplo de entrada | Exemplo de saída |
|
05 termo da sequencia de Fibonacci e 5. |
|
06 termo da sequencia de Fibonacci e 8. |
Passo 1
Beleza, vamos lá! O problema pede para a gente criar uma função recursiva que retorne o n-ésimo termo da sequência de Fibonacci. A sequência de Fibonacci é essa famosa onde cada número é a soma dos dois anteriores, começando com 0 e 1. Para resolver isso, vamos precisar entender o que é recursão na programação e como ela pode nos ajudar a calcular os termos da sequência.
Passo 2
Primeiro, vamos relembrar como a sequência de Fibonacci funciona:
E para qualquer $ n > 1 $:
Isso significa que para encontrar $ F(n) $, a gente precisa conhecer os dois termos anteriores.
Passo 3
Agora, vamos pensar em como implementar isso em uma função recursiva. Recursão é quando uma função chama a si mesma para resolver subproblemas menores. No nosso caso, a função vai chamar a si mesma para calcular $ F(n-1) $ e $ F(n-2) $.
Passo 4
Vamos definir a função. Vou usar Python como exemplo, mas a lógica é a mesma em outras linguagens. A função vai receber um número $ n $ e retornar o $ n $-ésimo termo da sequência.
Passo 5
Dentro da função, vamos estabelecer os casos base:
- Se $ n == 0 $, retorna 0.
- Se $ n == 1 $, retorna 1.
Esses são os pontos onde a recursão para, evitando um loop infinito.
Passo 6
Se $ n $ for maior que 1, a função vai chamar a si mesma para calcular $ F(n-1) $ e $ F(n-2) $, e então retornar a soma desses dois valores.
Passo 7
Vamos ver como fica o código completo:
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
Resposta
Pronto! Agora, se você chamar a função
fibonacci
com $ n = 5 $, ela vai retornar 5
, e com $ n = 6 $, vai retornar 8
, exatamente como nos exemplos. Por exemplo:print(fibonacci(5)) # Saída: 5
print(fibonacci(6)) # Saída: 8