Java Оценка рекурсии

Question

Я просто работаю с простым алгоритмом рекурсии Фибоначчи, но я решил настроить его для дальнейшей проверки своих знаний рекурсии.

class fibonacci 
{ 
    static int fib(int n) 
    { 
    if (n <= 1) 
    return n; 
    int num = fib(n-1) + fib(n-2);
    num += 1;
    return num;
    } 

    public static void main (String args[]) 
    { 
    int n = 4; 
    System.out.println(fib(n)); 
    } 
} 

У меня возникают трудности с оценкой этого, потому что я получаю 7 в качестве результата, но когда я оцениваю это, я получаю 4. Может ли кто-нибудь объяснить шаг за шагом, что я делаю неправильно ? Спасибо!

Answer 1

У вас есть лишнее число + = 1, без причины я могу видеть. Я думаю, что вы пытаетесь исправить только те случаи, которые не прошли этот шаг.

По вашему коду:

fib(0) is 0
fib(1) is 1
fib(2) is fib(1) + fib(0) + 1 which is 2
fib(3) is fib(2) + fib(1) + 1 which is 4
fib(4) is fib(3) + fib(2) + 1 which is 7