Рекурсия

Вычисление факториала
Задача про 8 ферзей
Расстановка ферзей
Разделяй и властвуй

Числа Фибоначчи
Динамическое программирование
Упаковка рюкзака
Рекурсия без рекурсии ^*

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

Факториал определяется рекуррентным соотношением 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 страницу

Запуск скрипта даёт: 5!=120. Выше функция 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!=40320) приводят к ферзям на одной диагонали.

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

<style>
   .board { border:2px solid black; margin:4px; display:inline-block; }
   .cell  { border:1px solid black; width:20px; height:20px; font-size: 20px; display:inline-block; }
   .white { background-color:white; color:black;}
   .black { background-color:#555;  color:white;}
</style>

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

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

function Show()
{
   document.write('<div class="board">');         // открываем тег 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('<br>');                     // переход на новую строку
   }
   document.write('</div>');                      // закрываем тег 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 нашла 92 решения, первые 5 из которых приведены выше. Полный перебор потребовал 1965 рекурсивных вызовов функции. Ниже приведена последовательность первых расстановок ферзей, которые не привели к решению, хотя в начале всё получалось (проверьте, что на очередную пустую колонку на пятой картинке ферзя поставить нельзя):

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

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

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

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

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

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

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

19,1,13,7,23,3,11,17,5,2

   19,1,13,7,23,3,11,17,5,2
      19,1,13,7,2,3,11,17,5,23
         2,1,13,7,19,3,11,17,5,23
         1,2,13,7,19,3,11,17,5,23
            1,2,3,7,19,13,11,17,5,23
               1,2,3,7,5,11,13,17,19,23
                  1,2,3,5,7,11,13,17,19,23
               1,2,3,5,7,11,13,17,19,23

1,2,3,5,7,11,13,17,19,23

Чтобы множества элементов не пересекались, в 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, '<br><br>');
ar.sort();
document.write(ar, '<br><br>');
ar.sort( function(a, b) { return a < b? -1: (a > b? 1:0); } );
document.write(ar);

19,1,13,7,23,3,11,17,5,2

1,11,13,17,19,2,23,3,5,7

1,2,3,5,7,11,13,17,19,23

JavaScript
с ? r1: r2

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

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

Числа Фибоначчи определяются рекуррентным соотношением F_n=F_n-1+F_n-2, с начальными значениями F₀=0 и F₁=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<sub>',i,'</sub>=<b>', f[i],'</b>, ');
}

JavaScript
Цикл for

Цикл for аналогичен циклу в других языках программирования:

  for(действие_перед_началом; проверка_перед_итерацией; действие_после_итерации){ итерация }

В функции, сначала происходит задание начального значения индекса (i=2), затем указывается условие, которое должно быть истинным (true), чтобы итерация цикла сработала (i меньше длины массива). Наконец, третья (после точки с запятой) команда выполняется после очередной итерации (в нашем случае это i++, т.е. увеличение индекса на единицу: i=i+1).

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

f₂=1, f₃=2, f₄=3, f₅=5, f₆=8, f₇=13, f₈=21, f₉=34, f₁₀=55, f₁₁=89, f₁₂=144, f₁₃=233, f₁₄=377, f₁₅=610, f₁₆=987, f₁₇=1597, f₁₈=2584, f₁₉=4181, f₂₀=6765, f₂₁=10946, f₂₂=17711, f₂₃=28657, f₂₄=46368, f₂₅=75025, f₂₆=121393, f₂₇=196418, f₂₈=317811, f₂₉=514229, f₃₀=832040, f₃₁=1346269, f₃₂=2178309, f₃₃=3524578, f₃₄=5702887, f₃₅=9227465, f₃₆=14930352, f₃₇=24157817, f₃₈=39088169, f₃₉=63245986, f₄₀=102334155, f₄₁=165580141, f₄₂=267914296, f₄₃=433494437, f₄₄=701408733, f₄₅=1134903170, f₄₆=1836311903, f₄₇=2971215073, f₄₈=4807526976, f₄₉=7778742049, f₅₀=12586269025,

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

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)) даст 21. Впрочем, это крайне неэффективный способ. Дело в том, что в Fib1(n) приходится по несколько раз вызывать функцию с одним и тем же аргументом:

    F₅ = F₄ + F₃ = (F₃+F₂) + (F₂+F₁) = ( (F₂+F₁) + F₂ ) + (F₂+F₁) = ...

Это приводит к очень "ветвистым" деревьям рекурсивных вызовов с повторяющимися кустами веток (ниже построены вызовы Fib1(3), Fib1(5), Fib1(7) и в узлах деревьев приведено значение аргумента n):

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

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

n	2	3	4	5	6	7	10	20	30
F_n	1	2	3	5	8	13	55	6765	832040
N_n	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)) снова даст 21, однако, деревья рекурсивных вызовов получаются существенно компактнее:

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

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

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

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

∑ x_is_i ≤ size,       ∑ x_iv_i = 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,
               "<br>предметы : ");
 
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);

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

размер = 61 ценность = 77, число вызовов = 170
предметы : 1,1,5

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) при различных количествах предметов x_i=[x₀, x₁]:

x₁\x₀	0	1	2	3	4	5	6	7	8
0	0,0	1,1	2,2	3,3	4,4	5,5	6,6	7,7	8,8
1	2,3	3,4	4,5	5,6	6,7	7,8	8,9
2	4,6	5,7	6,8	7,9	8,10
3	6,9	7,10	8,11
4	8,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.

ИИ на JavaScript <

> Грубая сила