Рекурсия

Если вы не знакомы с рекурсивными функциями то вот определение из шести слов: это функция которая вызывает саму себя. Звучит просто, а на деле это мощно, сложно и опасно.

Когда я учился нас предостерегали использовать рекурсивные функции, и правильно: если не контролировать рекурсивную функцию она быстро взорвет ваш стек вызовов и приведет к падению программы. Чтобы сделать правильную рекурсивную функцию надо решить три вопроса:

1. Выделить базовый случай.
2. Выделить рекурсивный случай и изменение входных данных.
3. Доказать что изменение данных в рекурсивных случаях в конечном счете приведет к базовому случаю.

Базовый случай это такое состояние входных данных при котором функция завершает свою работу.

В противном случае происходит рекурсивный вызов. Это когда функция вызывает саму себя с новым набором данных, это могут быть измененные входные данные или совершенно другие.

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

Рассмотрим интересный пример — реализацию функции 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-ферзях. Предыдущий пост из этого цикла вас познакомил с деревьями, в этом посте мы научились их обрабатывать. В следующем посте мы наконец-то решим то, ради чего я все это затеял. Следите за обновлениями.