Não entendi o exercício do cálculo do número de Fibonacci.

Olá gab, tudo bem com você?

Fique tranquilo, pois recursão é um assunto bem complexo e difícil de perceber nas primeiras vezes, com o passar do tempo vai ficando um pouco mais fácil :)

Vou te auxiliar, simulando a execução de um programa ok?

Temos dois pontos principais em uma recursão que temos sempre que pensar:

• Condição de Parada: Em que momento nosso código pode parar de executar ?
• Diminuir o tamanho do problema: Como temos uma função que chama a si mesmo para que a gente "evolua" precisamos diminuir o problema em cada execução

Em relação a função de fibonacci temos:

1. Condição de Parada:

    if(n == 0) return 0;
    if(n == 1) return 1;

   Sabemos que o fibonacci de 1 e de 0, e não existe fibonacci negativo, então quando chegarmos nesse valor podemos apenas retornar o valor e não chamar novamente

2. Diminuir o tamanho do problema

    return fib(n-1) + fib(n-2);

Então aqui a gente está pegando um problema de tamanho n e diminuindo ele para um problema de tamanho n-1 e n-2

Agora vamos a execução do Fibonacci de 4

Então eu chamo a passando n = 4, teremos o seguinte fluxo:

>> fib(4)
 n == 0 ?  Falso
 n  == 1? Falso

Retorna o fib(3) + fib(2)

Então vamos calcular o fibonacci(3), veja que ainda não tocamos no fib(2)

>> fib(3)

  n == 0 ?  Falso
  n  == 1? Falso

Retorna o fib(2) + fib(1)

Novamente, vamos calcular o fibonacci(2):

>> fib(2)

n == 0 ?  Falso
n  == 1?  Falso

Retorna o fib(1) + fib(0)

E finalmente chegamos na condição de parada, vamos chamar fib(1)

>> fib(1)
  n == 0 ?  Falso
  n  == 1?  Verdadeiro --> Retorna 1 

Mas iremos retornar 1 para quem? para a execução anterior, então voltando para o fib(2) teremos:

Retorna o 1 + fib(0)

Vamos calcular o fib(0):

n == 0 ? Verdadeiro --> Retorna 0 

Retornamos para o fib(2) novamente:

Retorna 1 + 0 = 1, que é o resultado `fib(2)`

E agora voltamos para o fib(3)que foi quem chamou fib(2):

>> fib(3)

n == 0 ?  Falso
n  == 1? Falso

Retorna o 1 + fib(1)

Vamos calcular o fib(1), eu sei que já calculamos, mas o nosso programa não sabe disso:

>> fib(1)
  n == 0 ?  Falso
 n  == 1?  Verdadeiro --> Retorna 1 

Retorna para o fib(3)

>> fib(3)

 n == 0 ?   Falso
 n  == 1?  Falso

Retorna o 1 + 1 --> 2

Então temos fib(3) = 2, voltamos para quem chamou o fib(3) que foi o fib(4):

>> fib(4)
 n == 0 ?  Falso
 n  == 1?  Falso

Retorna o 2 + fib(2)

Teríamos que calcular da mesma forma o fib(2), vou pular isso para não ficar mais enorme, entretanto no final teríamos:

>> fib(4)
 n == 0 ?   Falso
n  == 1?  Falso

Retorna o  2 + 1 ---> 3

O retorno final do nosso programa de fib(4) é 3

Ou seja uma função recursiva vai chamando a si mesmo quebrando o problema em etapas menores, até chegar no tamanho mínimo, quando chega nisso ela começa a trazer o valor para quem chamou :)

Compreendeu? Qualquer coisa estou a disposição :)

Abraços e Bons Estudos!