ilyachalov (ilyachalov) wrote,
ilyachalov
ilyachalov

Categories:

Учебник по 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.)

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

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments