Рекурсия


Вычисление факториала

Факториал определяется рекуррентным соотношением n! = n · (n-1)!. В предыдущем документе он был вычислен в цикле. Этот же результат можно получить при помощи следующей функции:

function fac(n)
{
   if(n < 2) return 1;                            // для fac(1) вернём 1 (и вообще при n < 2)
   return n*fac(n-1);                             // рекурсия n! = n * (n-1)!
}

document.write("5!=", fac(5));                    // выводим значение функции на html страницу
Запуск скрипта даёт: . Выше функция fac вызывает сама себя с аргументом на 1 меньше. Это простейший пример рекурсии. При выполнении программы происходит цепочка вычислений fac(5) = 5*fac(4) = 5*( 4*fac(3) ) и т.д., пока вызовы не доберутся до fac(1) и не сработает первая строка функции.

При каждом рекурсивном вызове в памяти сохраняются все локальные переменные, объявленные внутри функции (в fac это только аргумент n). После захода в вызываемую функцию и её "отработки" эти переменные восстанавливаются и ход вычислений продолжается с того места, где был прерван. При этом локальные переменные в рекурсивно вызываемой функции находятся в отдельной памяти, отличной от памяти функции которая её вызвала.

В JavaScript при вызове функции можно опускать часть её аргументов. К примеру (довольно глупому), если по умолчанию fac() должно означать fac(5), можно написать:

function fac(n)
{
   if(n === undefined) n=5;                       // значение аргумента по умолчанию

   if(n < 2) return 1;
   return n*fac(n-1);
}
Тройное равенство в if означает, что переменная n сравнивается с зарезервированным словом undefined (не определено) без преобразования типов. В данном случае можно было бы использовать и двойное равенство. Однако, тройное - чуть быстрее, т.к. не приводит стоящие в нём сущности к одному типу.


Задача про 8 ферзей

Применим рекурсию к более интересной задаче:

На шахматной доске 8x8 необходимо расставить 8 ферзей так, чтобы ни один из них не оказался под ударом (ферзь ходит по прямым линиями: горизонтальным, вертикальным и диагональным).
Понятно, что если на вертикальной линии (колонке) уже находится ферзь, на неё другого ферзя ставить нельзя. Поэтому зададим положение ферзей при помощи одномерного массива queens размером size=8. Каждый элемент queens[c]==r этого массива равен высоте (номеру строки r) ферзя в колонке под номером "c":
var size = 8;                                     // размер доски
var queens = Array(size);                         // положение ферзей
for(var c=0; c < size; c++)                       // бежим по колонкам
   queens[c] = 0;                                 // всех ставим на первую строку (это не решение)
В одной строке два ферзя находится не могут, поэтому элементы массива, в решении задачи различны. Возможным решением будет перестановка чисел (0,1,2,3,4,5,6,7), однако большинство таких перестановок (а их 8!=) приводят к ферзям на одной диагонали.

Напишем функцию, которая рисует шахматную доску при помощи стилей. В html есть символы шахматных фигур, например, ферзь - это: &#9819; (16-битный unicode символа). В тегах style определим 4 класса стиля для шахматной доски (board), "бесцветной" клеточки (cell), а также белой (white) и чёрной (black) клеток:


Имя класса стиля начинается с точки и в фигурных скобках задаются его параметры. Доску мы окружаем толстым (2 пикселя) чёрным бордюром (border), вокруг которого делаем отступ в 4 пикселя (margin). Стили будут применяться к универсальному блоку html-страницы div. Последовательно идущие блоки div каждый раз начинаются с новой строки. Чтобы это пресечь (для вывода нескольких решений в одной строке) служит последний параметр класса board. Аналогично, задаётся бордюр, ширина (width), высота (height) и размер шрифта (font-size) для ячейки шахматной доски. Кроме этого, в классах white и black, определены белые и чёрные (серые) ячейки, в которых для контраста меняется не только цвет фона (background-color), но и цвет шрифта (color).

Теперь можно написать функцию печати доски:

function Show()
{
   document.write('
'); // открываем тег div for(var r=0; r < size; r++){ // по строкам for(var c=0; c < size; c++){ // по колонкам var ch = queens[c]===r ? "&#9819;" : " "; var knd = 'class="cell ' + ( (r+c) % 2 ? 'black"': 'white"'); document.write('<div ', knd, '>', ch, '</div>'); } document.write('
'); // переход на новую строку } document.write('
'); // закрываем тег div }

Первая и последняя строка функции окружают ячейки доски тегом div, которому устанавливается класс board. Затем в цикле по r сверху-вниз перебираются строки. Для каждой из них просматриваются колонки (цикл по c) и, если значение массива queens[c] совпадает с номером строки r, выводится ферзь, иначе - пробел (переменная ch).

JavaScript
Остаток от деления: x % 2
Затем выясняется чётность суммы r+c (остаток от деления на два равен 0 для 0,2,4,... и 1 для 1,3,5,...). При чётной сумме выбирается класс стиля class="cell white", а для нечётной: class="cell black" (комбинация двух классов в стиле объединяет их параметры).

Вывод доски в html-страницу, вообще говоря, лучше окружить тегами pre: <pre><script>Show()</script></pre>, чтобы ячейки не "разлазились".


Расстановка ферзей

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

В нашей задаче, соответственно, предположим, что n ферзей (n < 8) уже расставлены правильно и не угрожают друг другу. Добавим к ним ещё одного ферзя. Для этого необходимо задать элемент массива queens[n] (нумерация с нуля), т.е. определить высоту (номер строки) нового ферзя. Будем опускаться сверху вниз по строкам и для каждой из них проверять, не находится ли там ранее поставленный ферзь (первые n элементов массива queens). Кроме этого, необходимо проверить, что новый ферзь не оказался на одной диагонале со старыми. Пусть два ферзя имеют координаты (строка, столбец) равные (r1,c1) и (r2,c2). Они стоят на одной диагонали, если |r1-r2|===|c1-c2| (проверьте).

Код функции Solve, находящей все решения, имеет вид:

var nSolutions = 0;                               // число найденных решений

function Solve(n)
{
   if(n===undefined) n = 0;                       // вначале ферзей нет

   if(n >= size){                                 // всех расставили
      if(nSolutions++ < 5)                        // подсчитываем число решений
         Show();                                  // и выводим первые 5
      return;                                     // перебор окончен
   }

   for(var r=0, c; r < size; r++){                // бежим по строчкам сверху-вниз

      for(c=0; c < n; c++)                        // перебираем уже поставленных ферзей
         if(   queens[c] === r                    // если они стоят на этой строке
            || Math.abs(queens[c]-r) === n-c )    // или находятся с новым на одной диагонали
            break;                                // вариант не подходит - выходим из цикла

      if(c === n){                                // ни кто не бьет ферзя на r-той высоте
         queens[n] = r;                           // ставим его туда
         Solve(n+1);                              // и подбираем следующего - рекурсия!
      }
   }
}

Solve();                                          // запускаем функцию с 0 ферзями:


Всего функция Solve нашла решения, первые 5 из которых приведены выше. Полный перебор потребовал рекурсивных вызовов функции. Ниже приведена последовательность первых расстановок ферзей, которые не привели к решению, хотя в начале всё получалось (проверьте, что на очередную пустую колонку на пятой картинке ферзя поставить нельзя):

Алгоритму пришлось вернуться последнему шагу и опустить ферзя на нижнюю линию (с e5 на e1). Впрочем и это не помогает. Поэтому необходимо возвращаться ещё и ещё назад, пока второй ферзь не окажется на позиции b4 (т.е. queens[1]=4), что в конечном счёте приведёт к первому решению.

Разделяй и властвуй

При создании алгоритмов, часто используется приём, когда данные разбиваются на несколько частей (желательно равных) и алгоритм снова применяется к каждой из частей рекурсивным образом. Это можно сформулировать как: "разбей на подзадачи и реши их" или "разделяй и властвуй". Проиллюстрируем этот подход на примере задачи о "быстрой сортировки" массива.

Будем передавать в функцию qsort массив ar и диапазон индексов lf,...,rt между которыми элементы массива необходимо отсортировать по возрастанию (при первом вызове lf=0, а rt=ar.length-1, где ar.length - число элементов в массиве). Алгоритм состоит в следующем. Выберем некоторый элемент массива, который назовём "опорным" (ниже он расположен в середине массива). Затем будем переставлять элементы массива вокруг опорного так, чтобы слева от него оказалось множество элементов меньших, чем все элементы справа от них. Когда это произойдёт, применим рекурсивно алгоритм к левому и правому непересекающимся подмножествам элементов. Для случайных элементов, в среднем этот алгоритм требует n·log2(n) итераций по массиву:

function qsort(ar, lf, rt)
{
   if(lf === undefined) lf=0;                     // по умолчанию весь массив
   if(rt === undefined) rt=ar.length-1;

   var v = ar[(lf+rt) >> 1];                      // опорный - средний элемент
   var i = lf, j = rt;
   while(i <= j){                                 // пока i не превысило j

      while( ar[i] < v ) i++;                     // идём к v слева,  пока элементы меньше v
      while( v < ar[j] ) j--;                     // идём к v справа, пока элементы больше v

      if (i <= j){                                // нашлись "неправильные" элементы ar[i], ar[j]
         var  ai = ar[i]; ar[i]=ar[j]; ar[j]=ai;  // переставляем их местами (делаем "правильными")
         i++; j--;                                // продолжаем поиск "неправильных"
      }
   }

   if(lf < j) qsort(ar, lf,  j);                  // сортируем множество меньших значений
   if(i < rt) qsort(ar, i,  rt);                  // сортируем множество больших значений
}

JavaScript
n >> 1 === Math.floor(n/2)
Обратим внимание на способ получения среднего индекса: (lf+rt) >> 1. Логический сдвиг целого числа на один бит вправо эквивалентен целочисленному делению. Запись (lf+rt)/2 была бы не верной, т.к. при нечётной сумме получилось бы не целое число (JavaScript работает с вещественными числами!). Можно было бы отбросить дробную часть: Math.floor((lf+rt)/2), но приведенный способ целочисленного деления на 2 - быстрее и короче.

JavaScript
x | 0 === Math.floor(x)
Отметим ещё один трюк, связанный с числами. Пусть у числа x = 7.5 необходимо отбросить дробную часть. Можно написать: x = x | 0, что даст . Вертикальная черта означает целочисленную операцию "логического или". Видя её, браузер отбрасывает у x дробную часть и получившееся целое число логически "складывает" с нулём (целый x от этого не поменяется).

Протестируем функцию сортировки:

var ar = [19, 1, 13, 7, 23, 3, 11, 17, 5, 2];
document.write(ar, '

'); qsort(ar); document.write(ar);
Справа между первой строчкой (исходный массив) и последней (отсортированный) приведены вызовы функции (каждый отступ вправо соответствует более "глубокой" рекурсии). Синим цветом отмечены элементы ar[lf] и ar[rt], а красным - опорный элемент v. Обратим внимание, что опорный элемент также участвует в перестановках, поэтому не всегда получается разделять данные на равные части.

Чтобы множества элементов не пересекались, в while и if стоит проверка i <= j. Благодаря ей, рано или поздно, j станет на единицу меньше i. В результате, j окажется верхним индексом левого подмножества, а i - нижним правого (см. рекурсивные вызовы qsort). В if(i <= j) это иногда приводит к ненужной перестановке при i===j. Но это бывает редко, поэтому разбивать if на две части (i < j для первой строки и i <= j для второй) смысла не имеет. Функцию qsort можно чуть ускорить, если убрать if-ы в её начале (проверка на undefined аргументов). Для этого необходимо ввести две функции qsort(ar) и qsortLfRt(ar, lf, rt) и вторую функцию вызвать из первой.

В JavaScript существует встроенная функция sort, сортирующая массивы. Однако, она преобразует элементы массива к строкам, поэтому при сортировке чисел получается не совсем ожидаемый результат. Для устранения этого, необходимо при вызове sort передать ей в качестве аргумента функцию, которая возвращает -1, если элементы меньше друг друга и 1, если больше (а при равенстве вернуть 0). Эту функцию можно объявить как обычно, а затем передать её имя (только имя без скобок!), а можно создать безымянную функцию "налету":

var ar = [19, 1, 13, 7, 23, 3, 11, 17, 5, 2];
document.write(ar, '

'); ar.sort(); document.write(ar, '

'); ar.sort( function(a, b) { return a < b? -1: (a > b? 1:0); } ); document.write(ar);

JavaScript
с ? r1: r2
В безымянной функции использована конструкция (условие ? res_true: res_false), которая имеет значение res_true, если условие истинно и res_false - в противном случае. Выше эта конструкция использована дважды. Второй раз (a < b? 1:0) - равно 1, если a < b и 0 - иначе.


Числа Фибоначчи

Числа Фибоначчи определяются рекуррентным соотношением Fn=Fn-1+Fn-2, с начальными значениями F0=0 и F1=1. Несложно ими заполнить массив:

var f = new Array(51);                           // объявляем массив из 51 элемента
f[0]=0; f[1]=1;                                  // задаём начальные значения

for(var i=2; i < f.length; i++){                 // цикл по всем элементам массива, начиная с f[2]
   f[i] = f[i-1] + f[i-2];                       // применяем рекуррентную формулу
   document.write(' f',i,'=', f[i],', ');
}
JavaScript
Цикл for
Цикл for аналогичен циклу в других языках программирования:
  for(действие_перед_началом; проверка_перед_итерацией; действие_после_итерации){ итерация }
В функции, сначала происходит задание начального значения индекса (i=2), затем указывается условие, которое должно быть истинным (true), чтобы итерация цикла сработала (i меньше длины массива). Наконец, третья (после точки с запятой) команда выполняется после очередной итерации (в нашем случае это i++, т.е. увеличение индекса на единицу: i=i+1).

Вставка этого скрипта в html-документ (внутри тегов script) приводит к:

Чтобы выяснить некоторые проблемы, связанные с рекурсией, вычислим числа Фибоначчи также при помощи следующей функции:

function Fib1(n)
{
   if(n  <  1) return 0;                          // F0 = 0 - обрыв рекурсии
   if(n === 1) return 1;                          // сравниваем без преобразования типа (так быстрее!)

   return Fib1(n-1)+Fib1(n-2);                    // два рекурсивных вызова
}
В частности document.write(Fib1(8)) даст . Впрочем, это крайне неэффективный способ. Дело в том, что в Fib1(n) приходится по несколько раз вызывать функцию с одним и тем же аргументом:
    F5 = F4 + F3 = (F3+F2) + (F2+F1) = ( (F2+F1) + F2 ) + (F2+F1) = ...
Это приводит к очень "ветвистым" деревьям рекурсивных вызовов с повторяющимися кустами веток (ниже построены вызовы Fib1(3), Fib1(5), Fib1(7) и в узлах деревьев приведено значение аргумента n):

Для Fib1(7) значение Fib1(5) вычисляется два раза (выше синие узлы) и каждый такой вызов требует множества повторных вычислений. С ростом n число ветвей дерева стремительно растёт. Пусть количество вызовов равно Nn. Каждый вызов функции дополнительно порождает Nn-1 и Nn-2 вызовов и N0=N1=1. Поэтому:

Nn = 1 + Nn-1 + Nn-2.
Приведём некоторые значения чисел Фибоначчи и числа вызовов функции Fib1:

n 2 3 4 5 6 7 10 20 30
Fn 1 2 3 5 8 13 55 6765 832040
Nn 3 5 9 15 25 41 177 21891 2692537


Динамическое программирование

Проблема повторных рекурсивных вызовов функции обходится при помощи динамического программирования. Его идея состоит в сохранении всех вычисленных когда-либо значений функции. В результате, теряя в памяти, мы существенно выигрываем в быстродействии. При сохранении рекурсивности вызовов, подобных Fib1(n), числа Фибоначчи в этом подходе вычисляются следующим образом:

var fib = new Array(100);                         // массив объявлен, но его элементы === undefined

function Fib2(n)
{
   if(fib[n] !== undefined) return fib[n];        // уже знаем, сразу возвращаем

   if(n  <  1) return f[0]=0;
   if(n === 1) return f[1]=1;

   return fib[n] = Fib2(n-1)+Fib2(n-2);           // запоминаем новое значение и возвращаем его
}
что для document.write(Fib2(8)) снова даст , однако, деревья рекурсивных вызовов получаются существенно компактнее:

Выше массив объявлен при помощи оператора new, который создаёт объект Array (массив). Под этот массив резервируется память, однако 100 его элементов остаются неопределёнными (равными undefined). Этот факт используется в первой строке функции (оператор !== означает неравенство без приведения типов), чтобы принять решение - запускать рекурсию или сразу возвращать уже известные значения.

Заметим, что если функция Fib2 используется только один раз, можно в принципе уменьшить размер массива, храня только последние два значения функции с предыдущего уровня дерева рекурсивных вызовов.


Упаковка рюкзака

Рассмотрим теперь более содержательный пример применения динамического программирования. Пусть есть набор предметов, каждый из которых характеризуется "размером" s и "ценностью" v. Необходимо отобрать те из них (можно по несколько раз), которые поместятся в рюкзаке размером size и в сумме дадут максимальную ценность. Если через xi обозначить число предметов i-того вида, si - их размер и vi - ценности, задачу можно записать следующим образом:

 xisi ≤ size,        xivi = max;

Идея оптимальной упаковки состоит в следующем. Берём предмет, вычитаем его размер из размера рюкзака, получая тем самым "маленький рюкзак". Затем оптимально упаковываем этот "маленький рюкзак". Решение об упаковки предмета принимается, если суммарная ценность его и ценность "маленького рюкзака" максимальна.

Зададим массив предметов items, каждый из которых представим объектом с полями {s:размер, v:ценность}. Сразу введём массив уже вычисленных ранее значений функции (динамическое программирование) и число её вызовов:

var items = [ {s:1,v:1}, {s:5,v:6}, {s:11,v:14} ];// 3 вида предметов для упаковки

var values = new Array(1000);                     // массив значений функции pack
var numCalls    = 0;                              // число вызовов функции pack
Эти три переменные являются глобальными и "видны" (доступны) везде, в том числе внутри функции pack, которая возвращает ценность оптимально упакованного рюкзака размером size и номер "последнего" упакованного предмета:
function pack(size)                               // size - размер рюкзака
{
   numCalls++;                                    // подсчитываем число вызовов

   if(values[size] !== undefined)
      return values[size];                        // функция уже вычислялась

   var maxV = 0, maxI = -1;                       // максимум ценности и номер оптимального предмета
   for(var i=items.length; i--; ){                // ищем в списке items тот предмет,
      var space = size - items[i].s;              // добавление которого в рюкзак
      if( space >= 0 ){                           // (если это возможно)
         var  v  = pack(space).v + items[i].v;    // даст суммарную ценность v (рекурсия)
         if( v > maxV ){                          // если она максимальна,
            maxV = v; maxI = i;                   // запоминаем номер предмета в maxI
         }
      }
   }
   return values[size] = { v:maxV, i:maxI };      // возвращаем ценность рюкзака и последний предмет
}
Так как функция должна вернуть 2 значения (ценность рюкзака и номер предмета), результатом её работы является объект {v:ценность, i:номер_предмета}. Упакуем рюкзак размером size=61:
var res, size=61;
document.write("размер = ",size," ценность = ", pack(size).v,", число вызовов = ", numCalls,
               "
предметы : "); var x = new Array(items.length); // массив количеств предметов i-того типа for(var i=x.length; i--; ) x[i]=0; // обнуляем их while( (res = pack(size)).i >=0 ){ // выводим список предметов в рюкзаке x[res.i]++; size -= items[res.i].s; // уменьшаем размер и получаем следующий предмет } document.write(x);

Результат работы скрипта:


JavaScript
for: i++ или i--
Прокомментируем цикл по i в функции pack. Сперва i=items.length. Перед выполнением очередного цикла проверяется больше ли i нуля (i > 0). После этого i уменьшается на единицу (i--) и выполняется итерация цикла. В результате мы проходим по массиву от последнего элемента к первому (нулевому). Элементы массива можно перебрать и от первого к последнему: for(var i=0; i < items.length; i++). Приведенный в функции pack способ компактнее в записи, однако в Google Chrome оказывается слегка медленнее.

При выводе предметов, упакованных в рюкзак, в цикле while происходит следующее. Сначала результат функции сохраняется в переменной res. Затем (так как это объект) по точке "добираемся" до свойства i (номер предмета) и, если он не отрицателен, "крутимся" дальше. Внутри цикла происходит уменьшение размера рюкзака на размер упакованного i-того предмета.

Если закоментировать if в начале функции (отказаться от динамического программирования), то число вызовов функции увеличится до 8032306. Экономия получилась более, чем существенная. Причину этой экономии разберём на примере двух предметов: {s:1,v:1}, {s:2,v:3} и рюкзака размером size=8. Построим пространство поиска (таблицу заполненности и ценности рюкзака (s,v) при различных количествах предметов xi=[x0, x1]:

x1\x0 012345678
00,01,12,23,34,45,56,67,78,8
12,33,44,55,66,77,88,9
24,65,76,87,98,10
36,97,108,11
48,12

Видно, что одни и те же размеры (первая цифра) встречаются очень часто. Динамическое программирование один раз для данного размера запоминает оптимальную упаковку рюкзака и в дальнейшем расчёты не повторяет.


Рекурсия без рекурсии *

Иногда возникает необходимость контролировать процесс выполнения рекурсивных функций (например, для анимирования или взаимодействия с человеком). В этом случае можно строить вычисления, так же, как это "делает" компьютер. Идея разворачивания рекурсии состоит в сохранении каждого вызова функции, вместе с локальными переменными и аргументами в стеке. Стек - это очередь, в которую элементы помещаются в конец и от туда же извлекаются (первым вошёл - последним вышел). Ниже стек реализован при помощи обычного массива JavaScript. Кроме переменных в нём сохраняется также позиция в коде pos, куда необходимо вернуться после очередного рекурсивного вызова. Ниже код соответствует функции вычисления чисел Фибоначчи Fib1. Естественно, в этом случае такой способ не имеет смысла, однако точно также можно поступать и когда нет простого нерекурсивного алгоритма:

function FibStack(n)
{
   var res;                                       // итоговый результат работы
   var stack = [ {n:n, pos:0, res:0} ];           // первый вызов функции помещаем в стек
   while(stack.length){                           // пока стек не пустой
      var fun = stack.pop();                      // берём последний вызов
      switch(fun.pos){                            // переходим на нужное место в коде:
         case 0:
            if(fun.n < 1){
               fun.res = 0;                       // результат вычисления
               break;
            }
            if(fun.n === 1){
               fun.res = 1;                       // результат вычисления
               break;
            }
            fun.pos = 1;                          // следующий раз перейдём на case 1
            stack.push(fun);                      // сохраняемся перед рекурсией
            stack.push( {n:fun.n-1, pos:0,res:0});// рекурсивный вызов f(n-1)
            break;
         case 1:
            fun.res = res;                        // f[n] = f[n-1]
            fun.pos = 2;                          // следующий раз перейдём на case 2
            stack.push(fun);                      // сохраняемся перед рекурсией
            stack.push( {n:fun.n-2, pos:0,res:0});// рекурсивный вызов f(n-2)
            break;
         case 2:
            fun.res += res;                       // f[n] += f[n-2]
      }
      res = fun.res;                              // промежуточный результат работы
   }
   return res;                                    // итоговый результат работы
}

JavaScript
Ветвление switch
Выше использовано ветвление switch. В зависимости от значения целого числа fun.pos в аргументе команды switch( ... ) происходит переход к тому или иному блоку (участку) кода после команд "case значение:". Действие этого блока оканчивается командой break. Так, из 0-го case есть три выхода за пределы конструкции ветвления (2 в операторах if и один перед следующим case). В "case 1:" выход (break) один, а из последнего "case 2:" выход естественен, так как ниже закрываются фигурные скобки, ограничивающие область действия оператора ветвления switch. Важно помнить, что если в блоке case нет оператора break, управление передаётся в следующий блок case.