Еще одна интересная задача из учебника, которая в очередной раз показывает, почему рекурсию не следует использовать в реальных программах: «Числа Фибоначчи».
Числа Фибоначчи — это ряд натуральных (целых и положительных) чисел, каждое из которых (начиная с третьего) является суммой двух предыдущих:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233 и так далее...
https://ru.wikipedia.org/wiki/Числа_Фибоначчи
По условиям задачи требуется написать функцию, вычисляющую и возвращающую число из этого ряда чисел Фибоначчи по заданному номеру этого числа в этом ряду чисел.
Так как задача находится в подразделе 6.1 «Рекурсия и стек» учебника, то понятно, что предполагается, что ученик сначала попробует решить задачу методом рекурсии. Написать это решение несложно. Для проверки работы получившейся функции предлагается найти числа из ряда чисел Фибоначчи с номерами 3, 7 и 77.
Число с номером 3 из ряда чисел Фибоначчи — это число 2, с номером 7 — число 13, с номером 77 — число 5527939700884757.
И тут выясняется, что при поиске числа Фибоначчи с номером 77 вариант решения с рекурсией завешивает браузер (у меня — «Microsoft Edge») на некоторое время, после чего браузер выдает на экран сообщение о том, что «Эта страница не отвечает» (предлагается на выбор продолжить ожидание — кнопка «Wait», либо насильно завершить работу скрипта страницы — кнопка «Exit page»). Причины этого объяснены в указанном подразделе учебника.
Как я упоминал ранее (в учебнике это тоже подчеркивается), любую рекурсию можно переделать в цикл. Вариант решения с использованием цикла вместо рекурсии от авторов учебника:
function fib(n) {
let a = 1;
let b = 1;
for (let i = 3; i <= n; i++) {
let c = a + b;
a = b;
b = c;
}
return b;
}
Такое решение спокойно (без зависаний браузера) находит число с номером 77 из ряда чисел Фибоначчи. Причины этого неплохо изложены авторами учебника в их решении, рекомендую почитать.
Однако, мне кажется, у меня получилось решить эту задачу лучше (в смысле — понятнее).
Во-первых, неинформативное название переменных авторы учебника сами ругали в следующем подразделе учебника:
https://learn.javascript.ru/variables#pridumyvayte-pravilnye-imena
Переменные
a и b я назвал prev («предыдущее» число в ряде чисел Фибоначчи) и cur («текущее» число в ряде чисел Фибоначчи) соответственно. На каждой итерации цикла нам необходимо знать два числа из ряда чисел Фибоначчи, я их назвал «предыдущим» и «текущим».В цикле мы движемся по ряду чисел Фибоначчи в сторону увеличения чисел (вправо). В каждой новой итерации цикла «предыдущее» и «текущее» числа изменяются.
Новое «текущее» число вычисляется как сумма старого (из предыдущей итерации) «текущего» числа и старого (из предыдущей итерации) «предыдущего» числа. После этого старое «текущее» число становится новым «предыдущим» числом. Математическими инструкциями это можно выразить так:
curнов = curстар + prevстар
prevнов = curстар
Переменная
c, очевидно, является вспомогательной. Чтобы от нее избавиться, можно применить деструктурирующее присваивание, о котором в учебнике было рассказано ранее и я о нем писал. Преобразуя вышеприведенные математические формулы в JavaScript и применив деструктурирующее присваивание, получаем более изящный и более понятный, чем у авторов учебника, код:[cur, prev] = [cur + prev, cur];
Решение полностью:
function fib(n) {
let cur = 1, prev = 1;
for (let i = 3; i <= n; i++) {
[cur, prev] = [cur + prev, cur];
}
return cur;
}
