@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);
  • Вопрос задан
  • 529 просмотров
Решения вопроса 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.
Ответ написан
Ваш ответ на вопрос

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

Войти через центр авторизации
Похожие вопросы
До 170 000 руб.
IT IS Kernel Новосибирск
от 100 000 руб.
MERA Казань
от 120 000 руб.