@moreleaksILoveMS

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

Когда пытаешься понять, просто башка взрывается... Почему результат не 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);
  • Вопрос задан
  • 566 просмотров
Решения вопроса 1
sergiks
@sergiks Куратор тега JavaScript
♬♬
Числа Фибоначчи – это последовательность, начиная с 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'а сам позаботится о хранении промежуточных значений и цепочки кто-кого вызвал и с каким параметром.
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
sM0kfyz
@sM0kfyz
Frontend dev.
Во время выполнения кода в оперативной памяти создается вспомогательная структура называемая стеком. Она работает по принципу 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 в браузере. Чтобы визуализировать работу стека.
Ответ написан
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Всё из определения ряда Фибоначчи - следующий элемент ряда равен сумме двух предыдущих элементов.
А "девается" всё в стек. Изучайте, как работает стек вызовов функций в Javascript.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Stream Labs Москва
До 150 000 ₽
Myagi Минск
от 3 000 до 4 000 $
Salesbeat Москва
от 150 000 до 250 000 ₽
17 февр. 2020, в 00:30
1500 руб./за проект
16 февр. 2020, в 22:28
2000 руб./за проект
16 февр. 2020, в 22:03
1200 руб./в час