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 um 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, pesquise a matemática por trás da sequência de Fibonacci para ver se isso ajuda.
• Consulte a aba Recursos para encontrar informações relevantes!