Если вы не знакомы с рекурсивными функциями то вот определение из шести слов: это функция которая вызывает саму себя. Звучит просто, а на деле это мощно, сложно и опасно.
Когда я учился нас предостерегали использовать рекурсивные функции, и правильно: если не контролировать рекурсивную функцию она быстро взорвет ваш стек вызовов и приведет к падению программы. Чтобы сделать правильную рекурсивную функцию надо решить три вопроса:
- Выделить базовый случай.
- Выделить рекурсивный случай и изменение входных данных.
- Доказать что изменение данных в рекурсивных случаях в конечном счете приведет к базовому случаю.
Базовый случай это такое состояние входных данных при котором функция завершает свою работу.
В противном случае происходит рекурсивный вызов. Это когда функция вызывает саму себя с новым набором данных, это могут быть измененные входные данные или совершенно другие.
Очень важная часть структуры рекурсивных функций, которая, в отличии от предыдущих двух не отображается в программном коде это доказательство того, что изменение данных в рекурсивном случае приведет к базовому случаю. В некоторых случаях оно тривиально, в некоторых оно довольно сложно, но оно должно быть, иначе нет никакой гарантии того что ваша функция завершится.
Рассмотрим интересный пример — реализацию функции map. Это классическая функция, которая принимает массив данных d и применяет к каждому элементу функцию fn. В результате получается массив данных которые возвращает fn:
// @param {arrayof: x} d Данные
// @param {x -> y} fn Функция
var map = function(d, fn){
if(d.length==0){
return [];
}else{
var first = d[0];
var rest = d.slice(1,d.length);
return [fn(d[0])].concat(map(rest, fn));
}
};
// Проверим
var data = ["one", "two", "three"];
map(data, function(e){return "contains: " + e});
Разберем эту функцию в соответствии со структурой которую мы описали выше.
Базовый случай у нас это d.length==0, возвращается пустой массив.
В рекурсивной части происходят две интересные вещи:
- Создается массив с первым элементов входного массива и к нему конкатенируется результат рекурсивного вызова функции map.
- При рекурсивном вызове берется оставшаяся часть массива, без первого элемента, то есть количество данных уменьшается.
В данном случае доказательство того, что изменение данных приведет к базовому случаю очевидно: поскольку длинна входного массива больше нуля (а если ноль то это сразу базовый случай) и постоянно уменьшается то она достигнет нуля, следовательно и базового случая.
В этой функции рекурсивный вызов образует цикл натуральной рекурсии. Вот он показан наглядно:
Практика
Теперь вы. Попробуйте построить функцию filter которая принимает массив строк и строку поиска и возвращает все элементы массива которые равны этой строке поиска.
Взаимная рекурсия
А что же с нашими деревьями? В предыдущем посте я обещал, но так и не показал как их обрабатывать. Для того чтобы сделать это просто и быстро применим еще один крутой трюк — взаимную рекурсию.
Разобраться в этом трюке попробуем на примере. Представим себе кибер-дерево в узле которого может содержится яблоко в виде 1, 0 обозначает отсутствие яблока. Представим наше дерево визуально:
И в виде кода:
var n1 = {apple: 1, childs: []};
var n2 = {apple: 1, childs: []};
var n3 = {apple: 0, childs: []};
var n4 = {apple: 0, childs: []};
var n5 = {apple: 0, childs: [n1,n2,n3]};
var n6 = {apple: 1, childs: []};
var n7 = {apple: 1, childs: [n4]};
var root = {apple: 1, childs: [n7, n6, n5]};
Наша задача — пройтись по всему дереву и собрать все яблоки (единицы). Результат должен быть в виде массива яблок.
Алгоритм и решение
Давайте назовем нашу функцию harvest. На вход ей будет поступать дерево (узел с потомками), на выходе будет массив. Поскольку узел может содержать или не содержать яблоко нам надо обработать оба этих случая. Для простоты пока отбросим потомков. В случае если яблоко присутствует нам надо положить его в результирующий массив, который будет возвращен в результате работы функции. Поскольку мы пока отбросили потомков в случае отсутствия яблока у узла нам делать ничего не надо:
// @param {object: tree} Дерево
// @return {arrayof: 1} Массив яблок
var harvest = function(tree){
if(tree.apple==1){
return [1];
}else{
// яблока нет
}
};
А теперь подумаем о потомках нашего дерева. Потомки содержатся в поле childs нашего узла и представлены в виде массива таких же узлов. Давайте пожелаем чтобы у нас была функция harvestChilds которая обрабатывает этих потомков. Сделаем для нее заглушку, так мы сможем закончить нашу функцию harvest, а к новой функции вернемся позже:
// !!! - оставим для себя отметку что эта функция не реализована
var harvestChilds = function(){}
Вернемся к функции harvest. Если у нас есть яблоко сейчас мы возвращаем [1], то есть только яблоко текущего узла, при этом мы никак не учитываем потомков. Давайте представим что наша функция harvestChilds возвращает массив яблок потомков, если это так тогда нам надо к нашей единице прибавить этот массив. Мы это уже делали в функции map используя метод concat, в этом случае поступим так же.
В случае отсутствия яблока нам надо просто вернуть массив который возвращает harvestChilds для потомков этого узла. Как интересный побочный эффект наших раздумий о функции harvest мы узнали больше о функции harvestChilds, она должна принимать массив потомков и возвращать массив яблок этих потомков. Теперь отразим все наши пожелания относительно функции harvest и harvestChilds в коде:
// @param {object: tree} Дерево
// @return {arrayof: 1} Массив яблок
var harvest = function(tree){
if(tree.apple==1){
return [1].concat(harvestChilds(tree.childs));
}else{
return harvestChilds(tree.childs);
}
};
// !!! - оставим для себя отметку что эта функция не реализована
// @param {arrayof: tree} childs Потомки дерева
// @return {arrayof: 1} Яблоки, собранные с потомков
var harvestChilds = function(childs){
return [];
};
С harvest вроде разобрались, перейдем к harvestChilds. Как мы уже знаем она должна обработать каждый элемент массива потомков, который ей был передан, и вернуть массив яблок которые содержат эти потомки. Все это, опять же, похоже на нашу функцию map, поэтому давайте и эту функцию реализуем в рекурсивном стиле.
Мы уже знаем что для того чтобы создать хорошую рекурсивную функцию надо определить базовую и рекурсивную часть и доказать что рекурсивная часть приведет к базовой.
Рассмотрим базовый случай. Нам надо обработать каждый элемент массива. В функции map мы постоянно уменьшали входной массив и когда он становился пустым наступал наш базовый случай. Воспользуемся этим трюком и тут.
Что будем возвращать в базовом случае? Поскольку в процессе разработки функции harvest мы пожелали чтобы наша функция harvestChilds возвращала массив, тогда наш базовый случай будет возвращать пустой массив. Представим наши изменения в виде кода:
// !!! - оставим для себя отметку что эта функция не реализована
// @param {arrayof: tree} childs Потомки дерева
// @return {arrayof: 1} Яблоки, собранные с потомков
var harvestChilds = function(childs){
if(childs.length==0){
return []; // базовый случай
}else{
// рекурсивный случай
}
};
Осталось самое интересное — рекурсивный случай. На входе нас ждет массив поддеревьев-потомков, каждый элемент которого надо обработать следующим образом: если у элемента есть яблоко тогда надо прибавить к результирующему массиву один элемент, если яблока нет... Так, стоп. Догадались? У нас уже есть функция которая это делает — harvest.
Мы подошли к ключевому моменту — созданию цикла взаимной рекурсии. Давайте взглянем на функцию harvest. Для своих потомков она вызывает функцию harvestChilds, а harvestChilds для каждого потомка будет вызывать функцию harvest и так далее. Таким образом мы обработаем все наше дерево слево-направо. Представим работу алгоритма визуально, зеленым подсвечиваются обработанные узлы на данном шаге:
Заметим так же очень интересный факт — поскольку наши данные в виде деревьев имеют взаимную ссылку (потомок является тем же типом данных что и родитель) и функция у нас получилась со взаимной ссылкой. Подумайте над этим.
Но вернемся к нашему коду. Каждый элемент массива потомков мы будем обрабатывать функцией harvest, которая возвращает массив. Для того чтобы обработать не только первого потомка, но и всех остальных нам надо рекурсивно вызвать функцию harvestChilds и передать ей массив потомков из которого исключен первый потомок, потомок который мы уже обработали. Результат этой функции надо прицепить к результату обработки первого потомка, как мы это делали в функции map. Открываем редактор, тянем руки к клавиатуре, поехали:
// @param {arrayof: tree} childs Потомки дерева
// @return {arrayof: 1} Яблоки, собранные с потомков
var harvestChilds = function(childs){
if(childs.length==0){
return []; // базовый случай
}else{
// рекурсивный случай
var first = childs[0];
var rest = childs.slice(1, childs.length);
return harvest(first).concat(harvestChilds(rest));
}
};
Посмотрим на программу целиком:
var n1 = {apple: 1, childs: []}
var n2 = {apple: 1, childs: []}
var n3 = {apple: 0, childs: []}
var n4 = {apple: 0, childs: []}
var n5 = {apple: 0, childs: [n1,n2,n3]}
var n6 = {apple: 1, childs: []}
var n7 = {apple: 1, childs: [n4]}
var root = {apple: 1, childs: [n7, n6, n5]}
// @param {object: tree} Дерево
// @return {arrayof: 1} Массив яблок
var harvest = function(tree){
if(tree.apple==1){
return [1].concat(harvestChilds(tree.childs));
}else{
return harvestChilds(tree.childs);
}
};
// @param {arrayof: tree} childs Потомки дерева
// @return {arrayof: 1} Яблоки, собранные с потомков
var harvestChilds = function(childs){
if(childs.length==0){
return []; // базовый случай
}else{
// рекурсивный случай
var first = childs[0];
var rest = childs.slice(1, childs.length);
return harvest(first).concat(harvestChilds(rest));
}
};
Все вроде готово, давайте проверим. В нашем дереве root есть 5 яблок, следовательно если запуск функции harvest с деревом root возвратит нам меньше 5 яблок тогда мы что то сделали не так. Для продвинутых читателей предлагаю реализовать автоматический тест, а мы же просто запустим функцию:
harvest(root);
У меня вернулся массив из 5 яблок, если у вас что то не так сверьте ваш код с моим. Поздравляю, мы отлично поработали.
Выше мы представили визуально цикл натуральной рекурсии, давайте так же представим цикл взаимной рекурсии:
Практика
Небольшое задание для вас. Представим что у нас есть хтмл-дерево со структурой:
Представим эту структуру в виде объектов яваскрипта:
var p = {element: "p", id: "some-text", childs: []};
var li1 = {element: "li", id: "list-el-1", childs: []};
var li2 = {element: "li", id: "list-el-2", childs: []};
var ol = {element: "ol", id: "list", childs: [li1, li2]};
var img = {element: "img", id: "pic-of-me", childs: []};
var body = {element: "body", id: "", childs: [p, ol, img]};
var html = {element: "html", id: "", childs: [body]};
Ваша задача будет вывести в консоль все id элементов в этой структуре. Если у элемента нету id тогда ничего выводить в консоль не надо.
Заключение
Как видите рекурсия очень мощный механизм, который позволяет обрабатывать очень сложные структуры данных. Используйте ее аккуратно и разумно, не забывайте про ее структуру: базовый случай, рекурсивный случай, доказательство того что рекурсивные вызовы приведут к базовому случаю.
Так же напоминаю вам что мы уже в одном шаге от решения задачи о n-ферзях. Предыдущий пост из этого цикла вас познакомил с деревьями, в этом посте мы научились их обрабатывать. В следующем посте мы наконец-то решим то, ради чего я все это затеял. Следите за обновлениями.
