[Dúvida] Recursividade

Olá Gabriel, tudo bem?

Quando surge esse típo de dúvida, uma técnica interessante é tentar executar "(manua/menta)lmente" o código.

No caso do teu código em particular, vamos começar imaginando que sua função será chamada com o parâmetro "n = 0".

fib(0); // 0

int fib(int n) {
    // n=0, return 0
    if(n == 0) return 0;
    // nada é executado após o return
}

Para "n=1", acredito que você já entendeu qual será o resultado.

Agora vamos tentar "n=4"

fib(4); // 3

int fib(int n) { // n=4
    // ...

    // Chamamos a funcao fib() novamente,
    // agora passando o argumento n-1 e n-2
    // e somamos os resultados.
    //
    // fib(3) + fib(2)
    // 2 + 1
    // 3  
    return fib(n-1) + fib(n-2);
}

int fib(int n) { // n=3
    // ...

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

int fib(int n) { // n=2
    if(n == 0) return 0; // false
    if(n == 1) return 1; // false

    // fib(1) + fib(0)
    // 1 + 0
    // 1
    return fib(n-1) + fib(n-2);
}

Repeti a função no passo a passo para ficar bem claro o que estava acontecendo.

Recursividade

Só para esclarecer e ver se entendi, no fib(4) quando é chamado a função novamente em fib(3) + fib(2), para se ter o resultado de fib(4) terá que ser resolvido o fib(3) e depois fib(2). Seria isso?

Gabriel, seu entendimento está correto!

Uma outra forma de resolver essa questão seria utilizando uma estrutura de loop.

int fib(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;

    int prev1 = 0;
    int prev2 = 1;
    int result = 0;

    for (int i = 2; i <= n; i++) {
        result = prev1 + prev2;
        prev1 = prev2;
        prev2 = result;
    }

    return result;
}

Primeiro, verifica se o número fornecido n é igual a 0 ou 1 e retorna 0 ou 1, respectivamente, caso seja verdadeiro.

Em seguida, inicializa as variáveis prev1 e prev2 com os valores iniciais da sequência Fibonacci (0 e 1). A variável result é usada para armazenar o resultado da soma dos dois números anteriores.

O loop começa em i = 2 porque já calculamos os casos base para 0 e 1. Em cada iteração do loop, result é atualizado para a soma de prev1 e prev2, prev1 é atualizado para o valor anterior de prev2, e prev2 é atualizado para o valor atual de result.

Ao final do loop, o valor de result será o número Fibonacci correspondente ao número n fornecido e é retornado como resultado da função. Este método iterativo é mais eficiente do que o método recursivo para calcular números Fibonacci grandes, pois evita a sobrecarga de chamadas de função.