Recursão de Fibonacci

A sequência de Fibonacci é um caso clássico de uso de funções recursivas, pois o valor da sequência em determinado índice depende dos dois valores anteriores. Mais precisamente, ele depende da soma dos dois valores anteriores.

Escreva uma função chamada fib que receba um inteiro n como entrada. Ela deve retornar o valor da sequência de Fibonacci no índice n.

Exemplos

fib(6) ➞ 8
// 0 + 1 = 1, 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

fib(1) ➞ 1

fib(2) ➞ 1

Observações

• Considere que n sempre será um inteiro não negativo.
• Considere que os dois primeiros valores da sequência de Fibonacci (nos índices 0 e 1) são 0 e 1.
• Você deve fazer com que fib seja uma função recursiva.

Dicas

• Você pode chamar uma função dentro dela mesma para obter o valor retornado por outra iteração. Isso é chamado de "função recursiva".
• Se estiver com dificuldades, consulte os fundamentos matemáticos da sequência de Fibonacci para ver se eles ajudam você a encontrar a solução.
• Confira a aba Recursos para encontrar informações relevantes!