Почему рекурсивная последовательность фибоначчи работает?

Question

мне интересно, почему это рекурсивная функция Фибоначчи работает:

int fibRec(int n) 
{ 
    if ((n == 1) || (n == 0)) 
    { 
     return n; 
    } 

    int i = fibRec(n - 1) + fibRec(n - 2); 
    return i; 
} 

Я понимаю, что последовательность Фибоначчи, и я понимаю, что рекурсивная функция делает и как эта функция работает. У меня просто проблемы с пониманием Почему он работает. Я знаю, что когда вы его сломаете, вы по существу добавляете кучу 0 и 1, как показано на этом изображении.

fibonacci recursive

Но почему это, что, когда я прохожу 5 функции и все 0 и 1s добавляют, что он будет равен 5-й порядковый номер в последовательности Фибоначчи? Я уже видел этот вопрос, но никогда не объяснял. Ответы - это всего лишь «потому что рекурсия». Да, я знаю, что такое рекурсивная функция и как она работает. Но ПОЧЕМУ эта рекурсивная функция дает вам правильный порядковый номер Фибоначчи?

Answer 1

В последовательности Фибоначчи первые два числа равны нулю и единицам. Каждое число после них представляет собой сумму предыдущих двух чисел. Таким образом, первые несколько цифр являются

F(0) ≡ 0 
F(1) ≡ 1 
F(2) = F(1) + F(0) = 1 + 0 = 1 
F(3) = F(2) + F(1) = 1 + 1 = 2 
F(4) = F(3) + F(2) = 2 + 1 = 3 
F(5) = F(4) + F(3) = 3 + 2 = 5 
F(6) = F(5) + F(4) = 5 + 3 = 8 
... 
F(n) = F(n - 1) + F(n - 2) ∀ n > 1 

Поэтому при вычислении чисел Фибоначчи рекурсивно мы должны практиковать следующую логическую процедуру (в псевдокоде из уважения к StackOverflow).

Integer NthFibonacci(Integer n) { 
    if (n < 0) { 
     return undefined; 
    } else if (n < 2) { 
     return n; 
    } else { 
     return NthFibonacci(n - 1) + NthFibonacci(n - 2); 
    } 
} 

Я уверен, что вы знаете все это, но я думаю, что это поможет моему объяснению, чтобы эта часть была ссылкой.

Где Ones и Нули Come In

Лучший способ объяснить это, вероятно, с примером.

Представьте себе, что, как указано выше, мы пытаемся рекурсивно вычислить F(6). Попробуйте выполнить описанную выше процедуру. Помните, что мы выполним рекурсию, только если n> 1.

Сначала мы начинаем с F(6) = F(5) + F(4).
Затем мы находим F(5) = F(4) + F(3).
Затем мы находим F(4) = F(3) + F(2).
Затем мы находим F(3) = F(2) + F(1).
Затем мы находим F(2) = F(1) + F(0).

Здесь все наладилось!

В настоящее время мы получили F(2) с точкой зрения F(1) ≡ 1 и F(0) ≡ 0 (оба из которых известно), и поэтому мы можем рассчитать фактическое значение вместо выполнения более рекурсии.

Теперь мы можем найти F(2) = F(1) + F(0) = 1 + 0 = 1.

УВЕДОМЛЕНИЕ 1 И 0 Это то, о чем люди говорят, когда говорят, что все это сводится к единицам и нулям. Каждый раз, когда мы возвращаемся, чтобы найти базовое значение, мы получим F(2) = 1 + 0. Это приводит к увеличению числа и нулей в качестве . Мы возвращаемся к нашему дереву рекурсии, чтобы вычислять более высокие и более высокие значения, как показано ниже.

F(3) = F(2) + F(1) = (1 + 0) + 1 
F(4) = F(3) + F(2) = ((1 + 0) + 1) + (1 + 0) 
F(5) = F(4) + F(3) = (((1 + 0) + 1) + (1 + 0)) + ((1 + 0) + 1) 
F(6) = F(5) + F(4) = ((((1 + 0) + 1) + (1 + 0)) + ((1 + 0) + 1)) + (((1 + 0) + 1) + (1 + 0)) 

Теперь, если вы сложите все 1-х вы получаете сумму 8, и так F(6) = 8, что правильно!

Так оно и работает, и это то, как он разбивается на одни и на нули.

Answer 2

Помните, что рекурсия работает, разбивая проблему, пока мы не узнаем, что это за ответ, а затем построим ее оттуда.

Что мы узнаем о последовательности фибоначчи?

Мы знаем, что когда:

х = 1 и х = 0

То, что является самым низким он идет. Это важный ключ. Потому что, когда x = 0, мы действительно делаем 0 + 0, а когда x = 1, мы действительно делаем 0 + 1. Теперь начнем сверху.

0,1,1,2,3,5,8,13 ...

Если мы на 13. Что такое 13? Почему просто 5 + 8? Так вот где

int i = fibRec(n - 1) + fibRec(n - 2); 

происходит от. Потому что они будут разветвляться ниже и ниже, пока мы не будем в базовом случае для каждого.

Это рекурсивный вызов. Потому что теперь метод вернется в стек и снова вызовет fibRec. Вы заметите, что (n-1) и (n-2) объединяются вместе и устанавливаются в i. Это значит, что мы не теряем ценность. из-за знака + знак затем заканчивается тем, что возвращается все больше (n-1) s и (n-2) s, пока мы не будем в базовом случае. Надеюсь, все это имеет смысл. Мышление рекурсивно может быть очень сложным. Вот визуальное представление сверху донизу того, как оно будет выглядеть.

Короче. Это просто добавляет предыдущие последовательности фибоначчи к текущему, пока не попадет в текущий цикл.