как работает Фибоначчи с рекурсией

Question

int fib(int i) {
    if(i<2) {
        return 1;
    }
    else {
        return fib(i-1) + fib(i-2) ;
    }
}

Я не могу понять, как обрабатываются возвращаемые операторы fib(i-1) + fib(i-2) ???

Обрабатывается ли fib(i-1) сначала и fib(i-2) или оба обрабатываются одновременно ??

Кроме того, предположим, fib(i-1)=3, тогда в этом случае, как вычисляется fib(i-1)=3, я знаю, что это далее вызывается к fib(i-1)=2 и fib(i-1)=1, которые дают 1 в качестве возврата в обоих случаях.Тогда как вычисляется fib(i-1)=3 на основе fib(i-1)=2 и fib(i-1)=1 ???

Answer 1

fib(4) =                fib(3)                +                   fib(2)

                fib(2)        +       fib(1)     +           fib(1)    +     fib(0)

            fib(1) + fib(0)   +         1        +             1       +       1

              1   +   1       +         1        +             1       +       1     =    5

Answer 2

Каждый раз, когда он сталкивается с оператором return fib(i-1) + fib(i-2) ;, он должен выяснить, что такое fib(i-1) вначале, а затем, что fib(i-2) каждый раз.Каждый раз, когда я не выполняю требование быть меньше 2, оно должно идти к экземпляру return fib(i-1) + fib(i-2) ;.Затем он сначала ищет, что это за fib(i-1), а затем, что это за fib(i-2).Если fib(i-1) - это то, что заставило его перейти к другому экземпляру оператора else, то это означает, что он будет искать второй fib(i-1), а затем второй fib(i-2), прежде чем искать первый fib(i-2), поскольку эти вторые частинеобходимы, чтобы определить, что является первым fib(i-1).Он будет продолжать углубляться и углубляться в оператор else, если он не удовлетворяет требованиям if.Как только он получит свою первую 1 из оператора if, он сможет начать заполнять все значения для fib(i-1) s и fib(i-2) s, с которыми он ранее сталкивался, до тех пор, пока не вернется к первому fib(i-1).Только после этого он может перейти к первому fib(i-2) и спуститься туда, где ему необходимо, чтобы войти в if, прежде чем вводить эти 1 с и сложить их, чтобы найти именно то, что является первым return fib(i-1) + fib(i-2) ;.Если это только делает вещи более запутанными, я бы порекомендовал написать это со стрелками, указывающими, какие шаги предпринимаются, чтобы вы знали, где вы находитесь и что все было сделано более четко.Это помогло мне при первом изучении рекурсии с Фибоначчи.

Answer 3

Что-то вроде:

fib(4) = 
fib(3) + fib(2) = 
fib(2) + fib(1) + fib(2) = 
fib(1) + fib(0) + fib(1) + fib(2) = 
1 + fib(0) + fib(1) + fib(2) = 
1 + 1 + fib(1) + fib(2) = 
2 + fib(1) + fib(2) = 
2 + 1 + fib(2) = 
3 + fib(2) = 
3 + fib(1) + fib(0) = 
3 + 1 + fib(0) = 
4 + fib(0) = 
4 + 1 = 
5

Ничто не происходит "одновременно", оно просто вызывает fib несколько раз само по себе, в то время как ваш первый вызов fib(4).