March 27th, 2021

Учебник по JavaScript: ч.1, Рекурсия и стек

Начал читать шестой раздел («Продвинутая работа с функциями») первой части («Язык программирования JavaScript») учебника по JavaScript.

https://learn.javascript.ru

Часть 1. Язык программирования JavaScript (в т.ч. 93 подраздела)

Разделы:

6. Продвинутая работа с функциями (11 подразделов)

6.1 Рекурсия и стек

Раздел называется «Продвинутая работа с функциями», потому что про функции и работу с ними вкратце уже было рассказано в начале учебника и с тех пор почти во всех задачах (и примерах) требовалось написать какую-либо функцию.

В подразделе «Рекурсия и стек» рассказывается про рекурсивный вызов функции (то есть когда функция вызывает саму себя). Слово «стек» в названии подраздела не означает, что будет рассматриваться структура данных «стек»; тут имеется в виду запись контекста выполнения функции в стек при каждом обращении этой функции к самой себе (при каждом рекурсивном вызове).

Еще в подразделе рассказано про рекурсивный обход рекурсивной структуры данных. К примеру обход древообразной структуры данных или работа со связным списком. Забавно, как авторы учебника при этом стараются обойтись без введения понятий «адрес в памяти» и «переменная-ссылка».

Очень понравилась задача «Вычислить сумму чисел до данного». Сама задача простая, но задание состоит не просто в том, чтобы написать требуемую функцию. Предлагается написать требуемую функцию тремя (!) способами: с простым циклом, с рекурсией, с помощью формулы суммы арифметической прогрессии. Далее требуется объяснить, какая из этих функций будет самой медленной и неэффективной, а какая из трех — самой быстрой и эффективной.

Интуитивно было понятно, в каком порядке по производительности следует расположить получившиеся варианты функций. Но я использовал предложенный авторами учебника в одном из предыдущих подразделов (5.11 «Дата и время») способ определения быстродействия функций:

let start = Date.now();

for (let i = 0; i < 100000; i++) {
    // здесь вызываем нашу функцию
}

let end = Date.now();
alert( `Цикл отработал за ${end - start} миллисекунд` );

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

Получилось, что функция с простым циклом выполнила требуемую задачу на моем компьютере сто тысяч раз за 16 мс, функция с рекурсией — за 59 мс, а функция с формулой — за 3 мс. (Да, забыл написать, что в качестве тестового значения тестовой функции я брал число 100, то есть функция должна была вычислить сумму первых ста целых чисел, начиная с 1. Эта сумма равна 5050, это результат работы тестовой функции с тестовым значением 100.)

Что и требовалось доказать. Лично я в реальных программах ни разу не использовал рекурсию, я вообще ее недолюбливаю. Ведь любая рекурсия может быть переделана в цикл и, как правило, вариант с циклом будет эффективнее (об этом сказано жирным шрифтом и в данном учебнике, в этом подразделе).

Учебник по JavaScript: ч.1, Числа Фибоначчи

Начало в предыдущем посте: «Учебник по JavaScript: ч.1, Рекурсия и стек».

Еще одна интересная задача из учебника, которая в очередной раз показывает, почему рекурсию не следует использовать в реальных программах: «Числа Фибоначчи».

Числа Фибоначчи — это ряд натуральных (целых и положительных) чисел, каждое из которых (начиная с третьего) является суммой двух предыдущих:

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;
}