Как это работает (алгоритм с использованием рекурсии для вычисление числа Фибоначчи)?

Question

[CoyoteSS]

Когда пытаешься понять, просто башка взрывается... Почему результат не 13? (Ведь n (8) - 1 = 7 и n (8) - 2 = 6). Куда сохраняется всё это пока высчитывается число Фибоначчи? И зачем нужны эти (n - 1) с (n - 2) в функции?

function getFibonachi(n) {
  if (n == 0) {
    return 0;
  }
  if (n == 1) {
    return 1;
  }
  else {
    return getFibonachi(n-1) + getFibonachi(n-2);
  }
}

var result = getFibonachi(8);
console.log(result);

Answer 1

[Сергей Соколов]

Числа Фибоначчи – это последовательность, начиная с 0 и 1, где каждый следующий равен сумме двух предыдущих.

Третий равен 0 + 1 = 1 // итого первые три ряда: 0 1 1
Четвёртый это сумма последних двух единиц = 2 // 0 1 1 2
Пятый это 1 + 2 = 3 // 0 1 1 2 3
И так далее. Вот начало ряда:

значение:         0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144
порядковый номер: 0  1  2  3  4  5  6   7   8   9  10  11  12

Восьмой, если считать с 0, равен 21.

Параметром в функцию getFibonachi() передаётся не значение, а порядковый номер элемента ряда Фибоначчи, а функция должна вернуть значение.

Чтобы вычислить очередное значение, надо знать два предыдущих. Отсюда и (n-1) и (n-2)

Поскольку любой элемент ряда считается одинаково, пишут всего одну функцию. Она сразу готова дать ответ для первых двух элементов, если n = 0 или 1. В остальных случаях ей придётся вызывать саму себя.

Движок JavaScript'а сам позаботится о хранении промежуточных значений и цепочки кто-кого вызвал и с каким параметром.

Answer 2

[Ivan Sharapenkov]

Во время выполнения кода в оперативной памяти создается вспомогательная структура называемая стеком. Она работает по принципу LIFO - последний вошел - первый вышел. Когда вы вызываете функцию некоторые ее данные добавляются в стек - аргументы, расположение в памяти, адрес возврата (вообще эти данные зависят от реализации).
То есть когда вы вызвали getFibonachi(8) в стеке создалась запись о этом вызове. При этом n == 8. То есть мы попадаем в else и вызываем getFibonachi(7). Теперь стек имеет запись о двух функциях. И т.д. До тех пор пока n == 1. Тогда функция вернет 1. Эта последняя функция удаляется из стека. То есть на этом этапе стек содержит функции:
getFibonachi(2)
getFibonachi(3)
getFibonachi(4)
getFibonachi(5)
getFibonachi(6)
getFibonachi(7)
getFibonachi(8)
Мы возвращаемя к выполнению функции вызванной с аргументом 2. В этот момент мы рассчитывали функцию getFibonachi(1) (она была успешно вычислена и вернула 1) и теперь переходим к второму слагаемому. getFibonachi(0) (т.к n==2). Она возвращает 0. Теперь мы можем вычислить функцию getFibonachi(2), потому что мы уже получили значения от двух функций, которые были вызваны в блоке else. getFibonachi(2) вернет 1 (1+0=1) и удалится из стека. Теперь он выглядит так:
getFibonachi(3)
getFibonachi(4)
getFibonachi(5)
getFibonachi(6)
getFibonachi(7)
getFibonachi(8)
Продолжаем выполнение функции с вершины стека. И так далее пока все функции не вернут значения)) Более подробно гуглите: стек вызовов функции. Немного криво, но как смог.
Можете использовать дебаггер js в браузере. Чтобы визуализировать работу стека.

Comments

[Денис Загаевский]

Всё круто, только стек для Фибоначчи будет выглядеть не так.

[Ivan Sharapenkov]

Денис Загаевский, А как же он будет выглядеть?)

Answer 3

[Rsa97]

Всё из определения ряда Фибоначчи - следующий элемент ряда равен сумме двух предыдущих элементов.
А "девается" всё в стек. Изучайте, как работает стек вызовов функций в Javascript.

Comments

[CoyoteSS]

Я так понимаю вычитывается это всё так:
(8 - 1) + (8 - 2) = 13
(7 - 1) + (6 - 2) = 10
(6 - 1) + (4 - 2) = 7
(5 - 1) + (2 - 2) = 4
(4 - 1) + (0) = error! return sum (13 + 10 + 7 + 4) = 34

[Rsa97]

moreleaksILoveMS, Нет. Вычисляется не n-1, а функция от n-1.
F(8) = F(8-1) + F(8-2) = F(7) + F(6) = 21 + 13 = 34
F(7) = F(7-1) + F(7-2) = F(6) + F(5) = 13 + 8 = 21
F(6) = F(6-1) + F(6-2) = F(5) + F(4) = 8 + 5 = 13
F(5) = F(5-1) + F(5-2) = F(4) + F(3) = 5 + 3 = 8
F(4) = F(4-1) + F(4-2) = F(3) + F(2) = 3 + 2 = 5
F(3) = F(3-1) + F(3-2) = F(2) + F(1) = 2 + 1 = 3
F(2) = F(2-1) + F(2-2) = F(1) + F(0) = 1 + 1 = 2
F(1) = 1
F(0) = 1