Problema: A sequência de Fibonacci é definida como:
l F(0)=0, F(1)=1 F(n)=F(n-1)+F(n-2) para n>1
Escreva uma função recursiva que retorne o n-ésimo termo da sequência de Fibonacci, sendo n dado.
Exemplo de entrada Exemplo de saída
|ll| hline Exemplo de entrada & Exemplo de saída hline $5 backslash n$ & 05 termo da sequencia de Fibonacci e 5 hline $6 backslash n$ & 06 termo da sequencia de Fibonacci e 8 hline 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:
F(0) = 0, F(1) = 1
E para qualquer $ n > 1 $:
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

Exercícios relacionados