Возможно, вы встречали ссылки на рекурсивные функции при программировании на JavaScript. Возможно, вы даже пытались построить (или деконструировать) несколько самостоятельно. Но вы, вероятно, не видели много примеров эффективной рекурсии в дикой природе. На самом деле, кроме экзотической природы этого подхода, вы, возможно, не подумали, когда и где рекурсия полезна, или насколько опасной она может быть при небрежном использовании.
Для чего нужна рекурсия?
Рекурсия — это метод перебора операции, при котором функция сама вызывает несколько раз, пока не достигнет результата. Большинство циклов могут быть переписаны в рекурсивном стиле, и в некоторых функциональных языках этот подход к циклу используется по умолчанию.
Однако, хотя функциональный стиль кодирования JavaScript поддерживает рекурсивные функции, мы должны знать, что большинство компиляторов JavaScript в настоящее время не оптимизированы для их безопасной поддержки.
Рекурсия лучше всего применяется, когда вам нужно повторно вызывать одну и ту же функцию с разными параметрами внутри цикла. Хотя его можно использовать во многих ситуациях, он наиболее эффективен для решения задач, связанных с итеративным ветвлением, таких как фрактальная математика, сортировка или обход узлов сложных или нелинейных структур данных.
Одна из причин, по которой рекурсия предпочитается в функциональных языках программирования, заключается в том, что она позволяет создавать код, который не требует установки и поддержания состояния с помощью локальных переменных. Рекурсивные функции, естественно, также легко тестируются, потому что их легко написать чистым способом, с конкретным и непротиворечивым возвращаемым значением для любого заданного ввода и без побочных эффектов на состояния внешних переменных.
перекручивание
Классическим примером функции, в которой может быть применена рекурсия, является факториал. Это функция, которая возвращает значение умножения числа снова и снова на каждое предыдущее целое число, вплоть до единицы.
Например, факториал трех:
3 × 2 × 1 = 6 Факториал шести:
6 × 5 × 4 × 3 × 2 × 1 = 720
Вы можете видеть, как быстро эти результаты становятся большими. Вы также можете видеть, что мы повторяем одно и то же поведение снова и снова. Мы берем результат одной операции умножения и умножаем его снова на единицу меньше второго значения. Затем мы делаем это снова и снова, пока не достигнем одного.
Используя цикл for, нетрудно создать функцию, которая будет выполнять эту операцию итеративно, пока не вернет правильный результат:
var factor = function(number) { var result = 1; var count; for (count = number; count > 1; count--) { result *= count; } return result; }; console.log(factor(6)); // 720
Это работает, но не очень элегантно с точки зрения функционального программирования. Мы должны использовать несколько локальных переменных, которые поддерживают и отслеживают состояние, чтобы поддерживать цикл for, а затем возвращать результат. Разве не было бы чище, если бы мы могли отказаться от цикла for и использовать более функциональный подход JavaScript?
Рекурсия
Мы знаем, что JavaScript позволит нам писать функции, которые принимают функции в качестве аргументов . Так что, если мы хотим использовать реальную функцию, которую мы пишем, и выполнить ее в контексте ее запуска.
Это вообще возможно? Вы держите пари, что это так! Например, возьмем случай простого цикла while:
var counter = 10; while(counter > 0) { console.log(counter--); }
Когда это сделано, значение counter изменилось, но цикл выполнил свою работу по распечатке каждого значения, которое он содержал, когда мы медленно высасывали из него состояние.
Рекурсивная версия того же цикла может выглядеть примерно так:
var countdown = function(value) { if (value > 0) { console.log(value); return countdown(value - 1); } else { return value; } }; countdown(10);
Вы видите, как мы вызываем функцию countdown прямо в определении функции countdown ? JavaScript справляется с этим как босс и просто делает то, что вы надеетесь. Каждый раз, когда выполняется countdown , JavaScript отслеживает, откуда он был вызван, а затем работает в обратном направлении через этот стек вызовов функций, пока не завершится. Наша функция также избегает изменения состояния любых переменных, но все же использует переданное значение для управления рекурсией.
Возвращаясь к нашему факториальному случаю, мы могли бы переписать нашу предыдущую функцию следующим образом, чтобы использовать рекурсию:
var factorial = function(number) { if (number <= 0) { // terminal case return 1; } else { // block to execute return (number * factorial(number - 1)); } }; console.log(factorial(6)); // 720
Написание кода таким образом позволяет нам описывать весь процесс без сохранения состояния без побочных эффектов. Также стоит обратить внимание на то, как мы сначала проверяем значение аргумента, передаваемого в функцию, прежде чем делать какие-либо вычисления. Мы хотим, чтобы все функции, которые будут вызывать себя, быстро и без проблем выходили, когда добирались до своего терминала. Для факториала, рассчитанного таким образом, случай терминала возникает, когда переданное число равно нулю или отрицательно (мы также можем проверить отрицательные значения и вернуть другое сообщение, если мы того пожелаем).
Оптимизация вызовов
Одна из проблем современных реализаций JavaScript заключается в том, что у них нет стандартного способа предотвратить бесконечное накопление рекурсивными функциями своих функций и поглощение памяти до тех пор, пока они не превысят мощность движка. Рекурсивные функции JavaScript должны отслеживать, откуда они были вызваны каждый раз, чтобы они могли возобновить работу в нужной точке.
Во многих функциональных языках, таких как Haskell и Scheme, это управляется с помощью метода, называемого оптимизацией хвостового вызова. При оптимизации хвостового вызова каждый последующий цикл в рекурсивной функции будет происходить немедленно, а не складываться в памяти.
Теоретически, оптимизация хвостового вызова является частью стандарта для ECMAScript 6, в настоящее время следующей версии JavaScript, однако она еще не полностью реализована на большинстве платформ.
Батут Функции
Существуют способы заставить JavaScript выполнять рекурсивные функции безопасным образом, когда это необходимо. Например, можно создать пользовательскую функцию батута для итеративного управления рекурсивным выполнением, сохраняя за раз только одну операцию в стеке. Функции батута, используемые таким образом, могут использовать способность JavaScript привязывать функцию к определенному контексту, чтобы отразить рекурсивную функцию по отношению к самой себе, создавая результаты по одному до тех пор, пока цикл не будет завершен. Это позволит избежать создания большого стека операций, ожидающих выполнения.
На практике использование функций батута обычно замедляет работу в пользу безопасности. Кроме того, большая часть элегантности и читабельности, которую мы получаем путем написания наших функций рекурсивным способом, теряется в сверточных кодах, необходимых для того, чтобы этот подход работал в JavaScript.
Если вам интересно, я призываю вас прочитать больше об этой концепции и поделиться своими мыслями в обсуждении ниже. Вы можете начать с небольшой статьи о StackOverflow , а затем исследовать некоторые эссе Дона Тейлора и Марка МакДоннелла , в которых более подробно рассказывается о взлетах и падениях батутов в JavaScript.
Мы еще не там
Рекурсия — это мощная техника, о которой стоит знать. Во многих случаях рекурсия является наиболее прямым способом решения сложной проблемы. Но до тех пор, пока ECMAScript 6 не будет реализован везде, где он нам нужен, с оптимизацией хвостовых вызовов, нам нужно быть очень осторожными в отношении того, как и где мы применяем рекурсию.