Вернемся к функциям и изучим их более подробно.
Нашей первой темой будет рекурсия .
Если вы не новичок в программировании, то, вероятно, оно вам знакомо, и вы можете пропустить эту главу.
Рекурсия — это шаблон программирования, который полезен в ситуациях, когда задачу можно естественным образом разделить на несколько задач одного типа, но более простых. Или когда задачу можно упростить до простого действия и более простого варианта той же задачи. Или, как мы скоро увидим, для работы с определенными структурами данных.
Когда функция решает задачу, в процессе она может вызывать множество других функций. Частичным случаем этого является случай, когда функция вызывает сама себя . Это называется рекурсия .
Для начала напишем функцию pow(x, n) , которая возводит x в натуральную степень n . Другими словами, умножает x само на себя n раз.
мощность(2, 2) = 4 мощность(2, 3) = 8 мощность(2, 4) = 16
Есть два способа реализовать это.
Итеративное мышление: цикл for :
функция pow(x, n) {
пусть результат = 1;
// умножаем результат на x n раз в цикле
for (пусть я = 0; я < n; я++) {
результат *= х;
}
вернуть результат;
}
оповещение(pow(2, 3)); // 8Рекурсивное мышление: упростите задачу и вызовите self:
функция pow(x, n) {
если (n == 1) {
вернуть х;
} еще {
вернуть x * pow(x, n - 1);
}
}
предупреждение(pow(2, 3)); // 8Обратите внимание, насколько принципиально отличается рекурсивный вариант.
При вызове pow(x, n) выполнение разделяется на две ветви:
если n==1 = x
/
pow(x, n) =
иначе = x * pow(x, n - 1) Если n == 1 , то всё тривиально. Ее называют базой рекурсии, потому что она сразу дает очевидный результат: pow(x, 1) равно x .
В противном случае мы можем представить pow(x, n) как x * pow(x, n - 1) . В математике можно было бы написать x n = x * x n-1 . Это называется рекурсивным шагом : мы преобразуем задачу в более простое действие (умножение на x ) и более простой вызов той же задачи ( pow с меньшим n ). Следующие шаги упрощают его все дальше и дальше, пока n не достигнет 1 .
Мы также можем сказать, что pow рекурсивно вызывает себя до n == 1 .
Например, для вычисления pow(2, 4) рекурсивный вариант выполняет следующие шаги:
pow(2, 4) = 2 * pow(2, 3)
pow(2, 3) = 2 * pow(2, 2)
pow(2, 2) = 2 * pow(2, 1)
pow(2, 1) = 2
Итак, рекурсия сводит вызов функции к более простому, а затем – к еще более простому и так далее, пока результат не станет очевидным.
Рекурсия обычно короче
Рекурсивное решение обычно короче итерационного.
Здесь мы можем переписать то же самое, используя условный оператор ? вместо if чтобы сделать pow(x, n) более кратким и при этом очень читабельным:
функция pow(x, n) {
возврат (n == 1) ? x : (x * pow(x, n - 1));
} Максимальное количество вложенных вызовов (включая первый) называется глубиной рекурсии . В нашем случае это будет ровно n .
Максимальная глубина рекурсии ограничена движком JavaScript. Мы можем рассчитывать на то, что это 10 000, некоторые двигатели позволяют больше, но 100 000, вероятно, выходят за пределы для большинства из них. Существуют автоматические оптимизации, которые помогают облегчить эту ситуацию («оптимизации хвостовых вызовов»), но они пока поддерживаются не везде и работают только в простых случаях.
Это ограничивает применение рекурсии, но оно по-прежнему остается очень широким. Есть много задач, где рекурсивный подход дает более простой код, который легче поддерживать.
Теперь давайте рассмотрим, как работают рекурсивные вызовы. Для этого мы заглянем под капот функций.
Информация о процессе выполнения запущенной функции хранится в ее контексте выполнения .
Контекст выполнения — это внутренняя структура данных, которая содержит подробную информацию о выполнении функции: где сейчас находится поток управления, текущие переменные, значение this (мы не используем его здесь) и некоторые другие внутренние детали.
С одним вызовом функции связан ровно один контекст выполнения.
Когда функция выполняет вложенный вызов, происходит следующее:
Текущая функция приостановлена.
Связанный с ним контекст выполнения запоминается в специальной структуре данных, называемой стеком контекста выполнения .
Вложенный вызов выполняется.
После его завершения старый контекст выполнения извлекается из стека, и внешняя функция возобновляется с того места, где она была остановлена.
Давайте посмотрим, что происходит во время вызова pow(2, 3) .
В начале вызова pow(2, 3) контекст выполнения будет хранить переменные: x = 2, n = 3 , поток выполнения находится в строке 1 функции.
Мы можем нарисовать это так:
Контекст: { x: 2, n: 3, в строке 1 } pow(2, 3)
Именно тогда функция начинает выполняться. Условие n == 1 неверно, поэтому поток продолжается во второй ветви if :
функция pow(x, n) {
если (n == 1) {
вернуть х;
} еще {
вернуть x * pow(x, n - 1);
}
}
предупреждение(pow(2, 3));Переменные те же, но строка меняется, поэтому контекст теперь такой:
Контекст: { x: 2, n: 3, в строке 5 } pow(2, 3)
Чтобы вычислить x * pow(x, n - 1) , нам нужно выполнить подвызов pow с новыми аргументами pow(2, 2) .
Чтобы выполнить вложенный вызов, JavaScript запоминает текущий контекст выполнения в стеке контекста выполнения .
Здесь мы вызываем ту же функцию pow , но это абсолютно не имеет значения. Процесс одинаков для всех функций:
Текущий контекст «запоминается» на вершине стека.
Для подвызова создается новый контекст.
Когда подвызов завершен — предыдущий контекст извлекается из стека, и его выполнение продолжается.
Вот стек контекста, когда мы вошли в подвызов pow(2, 2) :
Контекст: { x: 2, n: 2, в строке 1 } pow(2, 2)
Контекст: { x: 2, n: 3, в строке 5 } pow(2, 3)
Новый текущий контекст выполнения указан вверху (и выделен жирным шрифтом), а предыдущие запомненные контексты — внизу.
Когда мы завершаем подвызов — легко возобновить предыдущий контекст, поскольку он сохраняет как переменные, так и точное место кода, на котором он остановился.
Пожалуйста, обрати внимание:
Здесь на рисунке мы используем слово «строка», так как в нашем примере в строке только один подвызов, но обычно одна строка кода может содержать несколько подвызовов, например pow(…) + pow(…) + somethingElse(…) .
Поэтому точнее было бы сказать, что выполнение возобновляется «сразу после подвызова».
Процесс повторяется: в строке 5 выполняется новый подвызов, теперь с аргументами x=2 , n=1 .
Создается новый контекст выполнения, предыдущий помещается на вершину стека:
Контекст: { x: 2, n: 1, в строке 1 } pow(2, 1)
Контекст: { x: 2, n: 2, в строке 5 } pow(2, 2)
Контекст: { x: 2, n: 3, в строке 5 } pow(2, 3)
Сейчас есть 2 старых контекста и 1, работающий в настоящее время для pow(2, 1) .
Во время выполнения pow(2, 1) , в отличие от предыдущего, условие n == 1 является истинным, поэтому первая ветка if работает:
функция pow(x, n) {
если (п == 1) {
вернуть х;
} еще {
вернуть x * pow(x, n - 1);
}
} Вложенных вызовов больше нет, поэтому функция завершает работу, возвращая 2 .
По завершении функции контекст ее выполнения больше не нужен, поэтому он удаляется из памяти. Предыдущий восстанавливается с вершины стека:
Контекст: { x: 2, n: 2, в строке 5 } pow(2, 2)
Контекст: { x: 2, n: 3, в строке 5 } pow(2, 3)
Выполнение pow(2, 2) возобновляется. Он имеет результат подвызова pow(2, 1) , поэтому он также может завершить вычисление x * pow(x, n - 1) , вернув 4 .
Затем восстанавливается предыдущий контекст:
Контекст: { x: 2, n: 3, в строке 5 } pow(2, 3)
Когда он завершится, мы получим результат pow(2, 3) = 8 .
Глубина рекурсии в этом случае составила: 3 .
Как видно из иллюстраций выше, глубина рекурсии равна максимальному количеству контекстов в стеке.
Обратите внимание на требования к памяти. Контексты требуют памяти. В нашем случае возведение в степень n фактически требует памяти для n контекстов, для всех меньших значений n .
Алгоритм на основе цикла более экономит память:
функция pow(x, n) {
пусть результат = 1;
for (пусть я = 0; я < n; я++) {
результат *= х;
}
вернуть результат;
} Итеративный pow использует единственный контекст, изменяющий i и result процесса. Его требования к памяти невелики, фиксированы и не зависят от n .
Любую рекурсию можно переписать как цикл. Вариант с петлей обычно можно сделать более эффективным.
…Но иногда перезапись оказывается нетривиальной, особенно когда функция использует разные рекурсивные подвызовы в зависимости от условий и объединяет их результаты или когда ветвление более сложное. А оптимизация может оказаться ненужной и совершенно не стоящей затраченных усилий.
Рекурсия может дать более короткий код, более простой для понимания и поддержки. Оптимизации нужны не везде, чаще всего нужен хороший код, поэтому его и используют.
Еще одно замечательное применение рекурсии — рекурсивный обход.
Представьте, у нас есть компания. Структуру персонала можно представить в виде объекта:
пусть компания = {
продажи: [{
имя: 'Джон',
зарплата: 1000
}, {
имя: 'Алиса',
зарплата: 1600
}],
разработка: {
сайты: [{
имя: 'Питер',
зарплата: 2000
}, {
имя: Алекс,
зарплата: 1800
}],
внутренности: [{
имя: 'Джек',
зарплата: 1300
}]
}
};Другими словами, в компании есть отделы.
В отделе может быть множество сотрудников. Например, в отделе sales работают 2 сотрудника: Джон и Алиса.
Или отдел может разделиться на подотделы, например, у development есть две ветви: sites и internals . У каждого из них есть свой персонал.
Также возможно, что по мере роста подразделения оно разделяется на подразделения (или команды).
Например, отдел sites в будущем может быть разделен на команды для siteA и siteB И они, потенциально, могут расколоться еще больше. На картинке этого нет, просто надо иметь в виду.
Теперь предположим, что нам нужна функция, получающая сумму всех зарплат. Как мы можем это сделать?
Итеративный подход непрост, поскольку структура непроста. Первой идеей может быть создание цикла for по company с вложенным подциклом по отделам 1-го уровня. Но тогда нам нужно больше вложенных подциклов для перебора сотрудников в отделах 2-го уровня, таких как sites … А затем еще один подцикл внутри тех, что для отделов 3-го уровня, который может появиться в будущем? Если мы добавим в код 3-4 вложенных подцикла для обхода одного объекта, это станет довольно некрасиво.
Давайте попробуем рекурсию.
Как мы видим, когда наша функция суммирует отдел, возможны два случая:
Либо это «простой» отдел с набором людей — тогда мы можем просуммировать зарплаты в простом цикле.
Или это объект с N подотделами — тогда мы можем сделать N рекурсивных вызовов, чтобы получить сумму для каждого из подотделов и объединить результаты.
Первый случай — основа рекурсии, тривиальный случай, когда мы получаем массив.
Второй случай, когда мы получаем объект, — это рекурсивный шаг. Сложная задача разбивается на подзадачи для более мелких отделов. Они, в свою очередь, могут снова разделиться, но рано или поздно разделение закончится в (1).
Алгоритм, вероятно, еще проще прочитать из кода:
let Company = { // тот же объект, сжатый для краткости
продажи: [{имя: «Джон», зарплата: 1000}, {имя: «Алиса», зарплата: 1600 }],
разработка: {
сайты: [{имя: 'Пётр', зарплата: 2000}, {имя: 'Алекс', зарплата: 1800 }],
внутренности: [{имя: 'Джек', зарплата: 1300}]
}
};
// Функция для выполнения задания
функция sumSalaries(отдел) {
if (Array.isArray(department)) { // случай (1)
return Department.reduce((prev, current) => prev + current.salary, 0); // суммируем массив
} else { // случай (2)
пусть сумма = 0;
for (пусть подразделение Object.values(department)) {
sum += sumSalaries(subdep); // рекурсивно вызываем подотделы, суммируем результаты
}
сумма возврата;
}
}
оповещение (sumSalaries (компания)); // 7700Код короткий и простой для понимания (надеюсь?). В этом сила рекурсии. Это также работает для любого уровня вложенности подразделений.
Вот диаграмма звонков:
Мы легко можем увидеть принцип: для объекта {...} выполняются подвызовы, а массивы [...] являются «листьями» дерева рекурсии, они дают немедленный результат.
Обратите внимание, что в коде используются интеллектуальные функции, которые мы рассмотрели ранее:
Метод arr.reduce описан в главе «Методы массива» для получения суммы массива.
Цикл for(val of Object.values(obj)) для перебора значений объекта: Object.values возвращает их массив.
Рекурсивная (рекурсивно определяемая) структура данных — это структура, которая повторяет себя по частям.
Мы только что видели это на примере структуры компании выше.
Отдел компании – это:
Либо группа людей.
Или объект с отделами .
Для веб-разработчиков есть гораздо более известные примеры: документы HTML и XML.
В HTML-документе HTML-тег может содержать список:
Текстовые фрагменты.
HTML-комментарии.
Другие HTML-теги (которые, в свою очередь, могут содержать текстовые фрагменты/комментарии или другие теги и т. д.).
Это снова рекурсивное определение.
Для лучшего понимания мы рассмотрим еще одну рекурсивную структуру под названием «Связанный список», которая в некоторых случаях может быть лучшей альтернативой массивам.
Представьте, мы хотим хранить упорядоченный список объектов.
Естественным выбором будет массив:
пусть arr = [obj1, obj2, obj3];
…Но есть проблема с массивами. Операции «удалить элемент» и «вставить элемент» являются дорогостоящими. Например, операция arr.unshift(obj) должна перенумеровать все элементы, чтобы освободить место для нового obj , а если массив большой, это требует времени. То же самое с arr.shift() .
Единственные структурные модификации, которые не требуют массовой перенумерации, — это те, которые работают с концом массива: arr.push/pop . Таким образом, массив может быть довольно медленным для больших очередей, когда нам приходится работать с началом.
В качестве альтернативы, если нам действительно нужна быстрая вставка/удаление, мы можем выбрать другую структуру данных, называемую связанным списком.
Элемент связанного списка рекурсивно определяется как объект с помощью:
value .
next свойство, ссылающееся на следующий элемент связанного списка , или null , если это конец.
Например:
пусть список = {
значение: 1,
следующий: {
значение: 2,
следующий: {
значение: 3,
следующий: {
значение: 4,
следующий: ноль
}
}
}
};Графическое представление списка:
Альтернативный код для создания:
пусть список = {значение: 1};
list.next = {значение: 2};
list.next.next = {значение: 3};
list.next.next.next = {значение: 4};
list.next.next.next.next = ноль; Здесь мы можем еще более четко видеть, что существует несколько объектов, каждый из которых имеет value и next указывает на соседа. Переменная list является первым объектом в цепочке, поэтому по next указателям от нее мы можем добраться до любого элемента.
Список можно легко разделить на несколько частей, а затем соединить обратно:
пусть второй список = list.next.next; список.next.next = ноль;
Чтобы присоединиться:
list.next.next = второй список;
И, конечно же, мы можем вставлять или удалять элементы в любом месте.
Например, чтобы добавить новое значение, нам нужно обновить заголовок списка:
пусть список = {значение: 1};
list.next = {значение: 2};
list.next.next = {значение: 3};
list.next.next.next = {значение: 4};
// добавляем новое значение в список
list = {value: «новый элемент», next: list }; Чтобы удалить значение из середины, измените next из предыдущего:
список.следующий = список.следующий.следующий;
Мы сделали list.next переходом от 1 к значению 2 . Значение 1 теперь исключено из цепочки. Если он больше нигде не хранится, он будет автоматически удален из памяти.
В отличие от массивов, здесь нет массовой перенумерации, мы можем легко переставлять элементы.
Естественно, списки не всегда лучше массивов. В противном случае все бы использовали только списки.
Главный недостаток заключается в том, что мы не можем легко получить доступ к элементу по его номеру. В массиве это просто: arr[n] — это прямая ссылка. Но в списке нам нужно начать с первого элемента и пройти next N раз, чтобы получить N-й элемент.
…Но нам не всегда нужны такие операции. Например, когда нам нужна очередь или даже дек — упорядоченная структура, которая должна позволять очень быстро добавлять/удалять элементы с обоих концов, но доступ к ее середине не нужен.
Списки можно расширять:
Мы можем добавить свойство prev в дополнение к next , чтобы ссылаться на предыдущий элемент, чтобы можно было легко вернуться назад.
Мы также можем добавить переменную с именем tail ссылающуюся на последний элемент списка (и обновлять ее при добавлении/удалении элементов с конца).
…Структура данных может варьироваться в зависимости от наших потребностей.
Условия:
Рекурсия — это термин программирования, который означает вызов функции из самой себя. Рекурсивные функции можно использовать для элегантного решения задач.
Когда функция вызывает саму себя, это называется шагом рекурсии . Основой рекурсии являются аргументы функции, которые делают задачу настолько простой, что функция не выполняет дальнейших вызовов.
Рекурсивно определенная структура данных — это структура данных, которая может быть определена с использованием самой себя.
Например, связанный список можно определить как структуру данных, состоящую из объекта, ссылающегося на список (или нулевой).
список = { значение, следующий -> список }Деревья, такие как дерево элементов HTML или дерево отделов из этой главы, также естественно рекурсивны: у них есть ветви, и каждая ветвь может иметь другие ветви.
Для их обхода можно использовать рекурсивные функции, как мы видели в примере sumSalary .
Любую рекурсивную функцию можно переписать в итеративную. И это иногда требуется для оптимизации. Но для многих задач рекурсивное решение достаточно быстрое, его проще писать и поддерживать.
важность: 5
Напишите функцию sumTo(n) , которая вычисляет сумму чисел 1 + 2 + ... + n .
Например:
суммаTo(1) = 1 суммаTo(2) = 2 + 1 = 3 суммаTo(3) = 3 + 2 + 1 = 6 суммаTo(4) = 4 + 3 + 2 + 1 = 10 ... sumTo(100) = 100 + 99 + ... + 2 + 1 = 5050
Сделайте 3 варианта решения:
Использование цикла for.
Используя рекурсию, вызовите sumTo(n) = n + sumTo(n-1) для n > 1 .
Использование формулы арифметической прогрессии.
Пример результата:
function sumTo(n) { /*... ваш код ... */ }
Оповещение (сумма(100)); // 5050PS Какой вариант решения самый быстрый? Самый медленный? Почему?
PPS Можем ли мы использовать рекурсию для подсчета sumTo(100000) ?
Решение с использованием цикла:
функция sumTo(n) {
пусть сумма = 0;
for (пусть я = 1; я <= n; я++) {
сумма += я;
}
сумма возврата;
}
Оповещение (сумма(100));Решение с использованием рекурсии:
функция sumTo(n) {
если (n == 1) вернуть 1;
вернуть n + sumTo(n - 1);
}
Оповещение (сумма(100)); Решение по формуле: sumTo(n) = n*(n+1)/2 :
функция sumTo(n) {
вернуть n * (n + 1)/2;
}
Оповещение (сумма(100)); PS Естественно, формула — самое быстрое решение. Он использует только 3 операции для любого числа n . Математика помогает!
Петлевой вариант – второй по скорости. И в рекурсивном, и в циклическом варианте мы суммируем одни и те же числа. Но рекурсия включает в себя вложенные вызовы и управление стеком выполнения. Это также требует ресурсов, поэтому происходит медленнее.
PPS Некоторые движки поддерживают оптимизацию «хвостового вызова»: если рекурсивный вызов является самым последним в функции, без выполнения других вычислений, то внешней функции не нужно будет возобновлять выполнение, поэтому движку не нужно запомнить контекст его выполнения. Это снимает нагрузку с памяти. Но если движок JavaScript не поддерживает оптимизацию хвостовых вызовов (большинство из них этого не делают), возникнет ошибка: превышен максимальный размер стека, поскольку обычно существует ограничение на общий размер стека.
важность: 4
Факториал натурального числа — это число, умноженное на "number minus one" , затем на "number minus two" и так далее до 1 . Факториал числа n обозначается как n!
Мы можем написать определение факториала следующим образом:
н! = n * (n - 1) * (n - 2) * ...*1
Значения факториалов для разных n :
1! = 1 2! = 2 * 1 = 2 3! = 3 * 2 * 1 = 6 4! = 4 * 3 * 2 * 1 = 24 5! = 5 * 4 * 3 * 2 * 1 = 120
Задача — написать функцию factorial(n) которая вычисляет n! использование рекурсивных вызовов.
предупреждение(факториал(5)); // 120
PS Подсказка: n! можно записать как n * (n-1)! Например: 3! = 3*2! = 3*2*1! = 6
По определению факториал n! можно записать как n * (n-1)! .
Другими словами, результат factorial(n) можно вычислить как n умноженное на результат factorial(n-1) . И вызов n-1 может рекурсивно спускаться все ниже и ниже, пока не достигнет 1 .
функция факториал(n) {
вернуть (n != 1) ? п * факториал (п - 1): 1;
}
предупреждение(факториал(5)); // 120 Основой рекурсии является значение 1 . Мы также можем сделать здесь базисом 0 , это не имеет большого значения, но дает еще один рекурсивный шаг:
функция факториал(n) {
вернуть? п * факториал (п - 1): 1;
}
предупреждение(факториал(5)); // 120важность: 5
Последовательность чисел Фибоначчи имеет формулу F n = F n-1 + F n-2 . Другими словами, следующее число представляет собой сумму двух предыдущих.
Первые два числа — 1 , затем 2(1+1) , затем 3(1+2) , 5(2+3) и так далее: 1, 1, 2, 3, 5, 8, 13, 21... .
Числа Фибоначчи связаны с золотым сечением и многими природными явлениями вокруг нас.
Напишите функцию fib(n) , которая возвращает n-th число Фибоначчи.
Пример работы:
function fib(n) { /* ваш код */ }
оповещение (фиб (3)); // 2
оповещение (фиб (7)); // 13
оповещение (фиб (77)); // 5527939700884757 PS Функция должна быть быстрой. Вызов fib(77) должен занимать не более доли секунды.
Первое решение, которое мы могли бы здесь попробовать, — рекурсивное.
Числа Фибоначчи рекурсивны по определению:
функция фиб(п) {
вернуть n <= 1? n : фиб(n - 1) + фиб(n - 2);
}
предупреждение(фиб(3)); // 2
предупреждение(фиб(7)); // 13
// Фиб(77); // будет очень медленно! …Но для больших значений n это очень медленно. Например, fib(77) может зависнуть на некоторое время, съедая все ресурсы процессора.
Это потому, что функция выполняет слишком много подвызовов. Одни и те же ценности переоцениваются снова и снова.
Например, давайте посмотрим часть вычислений для fib(5) :
... фиб(5) = фиб(4) + фиб(3) фиб(4) = фиб(3) + фиб(2) ...
Здесь мы видим, что значение fib(3) необходимо как для fib(5) так и для fib(4) . Таким образом, fib(3) будет вызываться и оцениваться два раза совершенно независимо.
Вот полное дерево рекурсии:
Мы можем ясно заметить, что fib(3) вычисляется два раза, а fib(2) вычисляется три раза. Общий объем вычислений растет намного быстрее, чем n , что делает его огромным даже для n=77 .
Мы можем оптимизировать это, запоминая уже вычисленные значения: если значение, скажем, fib(3) вычисляется один раз, то мы можем просто повторно использовать его в будущих вычислениях.
Другой вариант — отказаться от рекурсии и использовать совершенно другой алгоритм на основе циклов.
Вместо перехода от n к более низким значениям мы можем создать цикл, который начинается с 1 и 2 , затем получает fib(3) как их сумму, затем fib(4) как сумму двух предыдущих значений, затем fib(5) и идет вверх и вверх, пока не достигнет необходимого значения. На каждом шаге нам нужно запомнить только два предыдущих значения.
Вот шаги нового алгоритма в деталях.
Начало:
// a = fib(1), b = fib(2), эти значения по определению равны 1 пусть а = 1, б = 1; // получаем c = fib(3) как их сумму пусть с = а + b; /* теперь у нас есть fib(1), fib(2), fib(3) а б в 1, 1, 2 */
Теперь мы хотим получить fib(4) = fib(2) + fib(3) .
Давайте сдвинем переменные: a,b получит fib(2),fib(3) , а c получит их сумму:
а = б; // теперь a = fib(2) б = с; // теперь b = fib(3) в = а + б; // с = фиб(4) /* теперь у нас есть последовательность: а б в 1, 1, 2, 3 */
Следующий шаг дает еще один порядковый номер:
а = б; // теперь a = fib(3)
б = с; // теперь b = fib(4)
в = а + б; // с = фиб(5)
/* теперь последовательность (еще одно число):
а б в
1, 1, 2, 3, 5
*/…И так далее, пока не получим нужное значение. Это намного быстрее, чем рекурсия, и не требует повторяющихся вычислений.
Полный код:
функция фиб(п) {
пусть а = 1;
пусть б = 1;
for (пусть я = 3; я <= n; я++) {
пусть с = а + b;
а = б;
б = с;
}
вернуть б;
}
предупреждение(фиб(3)); // 2
предупреждение(фиб(7)); // 13
предупреждение(фиб(77)); // 5527939700884757 Цикл начинается с i=3 , поскольку первое и второе значения последовательности жестко запрограммированы в переменных a=1 , b=1 .
Этот подход называется динамическим программированием «снизу вверх».
важность: 5
Допустим, у нас есть односвязный список (как описано в главе «Рекурсия и стек»):
пусть список = {
значение: 1,
следующий: {
значение: 2,
следующий: {
значение: 3,
следующий: {
значение: 4,
следующий: ноль
}
}
}
}; Напишите функцию printList(list) , которая выводит элементы списка один за другим.
Сделайте два варианта решения: с помощью цикла и с помощью рекурсии.
Что лучше: с рекурсией или без нее?
Циклический вариант решения:
пусть список = {
значение: 1,
следующий: {
значение: 2,
следующий: {
значение: 3,
следующий: {
значение: 4,
следующий: ноль
}
}
}
};
функция printList(список) {
пусть ТМП = список;
в то время как (тмп) {
оповещение(tmp.value);
ТМП = ТМП.следующий;
}
}
ПечатьСписок (список); Обратите внимание, что для обхода списка мы используем временную переменную tmp . Технически, вместо этого мы могли бы использовать list параметров функции:
функция printList(список) {
пока (список) {
оповещение (список.значение);
список = список.следующий;
}
} …Но это было бы неразумно. В будущем нам может понадобиться расширить функцию, сделать что-нибудь еще со списком. Если мы изменим list , то потеряем такую возможность.
Говоря о хороших именах переменных, list здесь — это сам список. Первый его элемент. И так должно оставаться. Это ясно и надежно.
С другой стороны, роль tmp — исключительно обход списка, как i в цикле for .
Рекурсивный вариант printList(list) следует простой логике: для вывода списка мы должны вывести текущий list элементов, затем сделать то же самое для list.next :
пусть список = {
значение: 1,
следующий: {
значение: 2,
следующий: {
значение: 3,
следующий: {
значение: 4,
следующий: ноль
}
}
}
};
функция printList(список) {
оповещение (список.значение); // выводим текущий элемент
если (список.следующий) {
printList(list.next); // делаем то же самое для остальной части списка
}
}
ПечатьСписок (список);Что теперь лучше?
Технически цикл более эффективен. Эти два варианта делают то же самое, но цикл не тратит ресурсы на вызовы вложенных функций.
С другой стороны, рекурсивный вариант короче и иногда проще для понимания.
важность: 5
Выведите односвязный список из предыдущей задачи. Выведите односвязный список в обратном порядке.
Примите два решения: используя цикл и рекурсию.
Рекурсивная логика здесь немного сложна.
Нам нужно сначала вывести остальную часть списка, а затем вывести текущий:
пусть список = {
значение: 1,
следующий: {
значение: 2,
следующий: {
значение: 3,
следующий: {
значение: 4,
следующий: ноль
}
}
}
};
функция printReverseList(список) {
если (список.следующий) {
printReverseList(list.next);
}
оповещение (список.значение);
}
printReverseList (список);
Вариант с циклом также немного сложнее, чем с прямым выходом.
Невозможно получить последнее значение в нашем list . Мы также не можем «вернуться назад».
Итак, что мы можем сделать, так это сначала просмотреть элементы в прямом порядке и запомнить их в массиве, а затем вывести то, что мы запомнили, в обратном порядке:
пусть список = {
значение: 1,
следующий: {
значение: 2,
следующий: {
значение: 3,
следующий: {
значение: 4,
следующий: ноль
}
}
}
};
функция printReverseList(список) {
пусть arr = [];
пусть ТМП = список;
в то время как (тмп) {
arr.push(tmp.value);
ТМП = ТМП.следующий;
}
for (пусть i = arr.length - 1; i >= 0; i--) {
оповещение(прибытие[я]);
}
}
printReverseList (список);Обратите внимание, что рекурсивное решение фактически делает то же самое: оно следует по списку, запоминает элементы в цепочке вложенных вызовов (в стеке контекста выполнения), а затем выводит их.