Рекурсия. Понятие и примеры

recursion

Для кого эта статья

Эта статья будет полезна новичкам, только начавши своё знакомство с js, но уже знающим, что такое функции и для чего они нужны, что такое область видимости переменных, а также умеющего пользоваться js-консолью. Для понимания некоторых примеров будет не лишним знать, что такое DOM, какие есть функции для работы с ней и что они делают. Также понадобится умение работать с css-свойствами html-елементов. Примеры, не описанные в статье, но присутствующие в архиве с исходными кодами будут понятны только если вы знакомы с canvas API.

Понятие рекурсии

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

Пусть нам необходимо вывести на консоль числа от 0 до n в обратном порядке. Не рекурсивное решение выглядит следующим образом (exp1.js):

1
2
3
4
5
function write(n) {
  for (var i = 0; i >= 0; i--) {
    console.log(n);
  }
}

Теперь рассмотрим рекурсивное решение. Напишем функцию, которое просто выводит число n на консоль.

1
2
3
function write(n) {
  console.log(n);
}

так как отрицательные числа выводить нам не нужно, то поставим ограничение

1
2
3
4
5
function write(n) {
  if (n >= 0) {
    console.log(n);
  }
}

Теперь у нас есть функция, которая выводить неотрицательное число на консоль, но нам нужно вывести числа от 0 до n. Для этого нам необходимо вызывать функцию write саму из себя, выводя перед каждым таким вызовом её аргумент и отнимая от него единицу, пока он не станет равным нулю и рекурсивные вызовы прекратятся. (exp2.js):

1
2
3
4
5
6
function write(n) {
  if(n >= 0) {
    console.log(n);
    write(n - 1);
  }
}

Количество вызовов функции совершённых из неё самой называется глубиной рекурсии. Максимальная глубина рекурсии ограничена. Ограничения в разных браузераx разные. В опере (12.00) и хроме это 16382, в моззиле (14.0.1) — 46141. Откуда такие странные цифры я не знаю и они были получены опытным путём. На практике мне приходилось сталкиваться с этим ограничением только если я ошибся и рекурсия была бесконечной.

Стек вызовов

Рассмотрим пример: (exp3.js)

1
2
3
4
5
6
function write(n) {
  if(n >= 0) {
    write(n - 1);
    console.log(n);
  }
}

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

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

Визуализация

Возможно, наглядно представить что такое рекурсия вам поможет этот пример.
Напишем функцию, которая вставляет в родительский div, другой div поменьше, затем в него div ещё меньше и т.д. Для более наглядной иллюстрации работы этой функции будем красить вставляемые div’ы в рандомные цвета.
Пусть у нас уже есть страничка с одним div’ом. Мы будем центрировать каждый дочерний div относительно своего родителя при помощи css-свойства margin. Так же, для достижения эстетической гармонии сделаем div’ы круглыми при помощи свойства border-radius. Если у вас старый браузер, то div’ы останутся квадратными (демо).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
<!DOCTYPE html>
<html>
<head>
<title>Recursion exaple</title>
<script type="text/javascript" src="recursion.js"></script> 
<style>
div {
  margin: 0 auto;
  /* Для того, что свойство margin-top работало нужна такая пляска с бубном */
  padding-top: 1px;
  border-radius: 50%
}
 
</style>
</head>
 
<body>
  <div style="width: 500px; height: 500px;"></div>
</body>
 
</html>

Сама функция и её вызов будет располагаться, как вы уже догадались, в файле recursion.js. У неё будет три параметра: div-родитель; коэффициент, умножая на который высоту и ширину родителя мы будем получать высоту и ширину дочернего div’а и количество вложенных друг в друга div’ов, не считая самого первого, уже имеющегося на страничке.
Напишем сначала функцию, для получения случайного целого числа из отрезка. До сих пор удивляюсь, что нет такой нативной функции в js.

1
2
3
function getRandomInt(min, max) {
  return Math.round(min + (max - min) * Math.random());
}

Функция получения рандомной интенсивности цветового канала:

1
2
3
4
5
6
7
function getRandomCanalIntensity() {
  var a = getRandomInt(0, 255).toString(16);
  if (a.length != 2) {
    a = '0' + a;
  }
  return a;
}

Функция получения рандомного цвета:

1
2
3
4
5
6
function getRandomColor() {
  var r = getRandomCanalIntensity(),
    g = getRandomCanalIntensity(),
    b = getRandomCanalIntensity();
  return '#' + r + g + b;
}

И, наконец, наша рекурсивная функция:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function appendDiv(parentDiv, k, n) {
  if (n > 0) {
    var width = parseInt(parentDiv.style.width),
      height = parseInt(parentDiv.style.height),
      childDiv = document.createElement('DIV');
 
    childDiv.style.width = width * k + 'px';
    childDiv.style.height = height * k + 'px';
    childDiv.style.marginTop = height * (1 - k) / 2 + 'px';
    childDiv.style.backgroundColor = getRandomColor();
    parentDiv.appendChild(childDiv);
    appendDiv(childDiv, k, n - 1);
  }
}

Получение первого div’a, его окраска в рандомный цвет и вызов рекурсивной функции после загрузки странички:

1
2
3
4
5
window.onload = function () {
  var parentDiv = document.getElementsByTagName('DIV')[0];
  parentDiv.style.backgroundColor = getRandomColor();
  appendDiv(parentDiv, 0.9, 20);
}

Демо

Тоже самое можно было сделать не прибегая к рекурсии, менее мозголомным способом.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function nestedDivs(parentDiv, k, n) {
  for(var i = 0; i < n; i++) {
    var width = parseInt(parentDiv.style.width),
      height = parseInt(parentDiv.style.height),
      childDiv = document.createElement('DIV');
 
    childDiv.style.width = width * k + 'px';
    childDiv.style.height = height * k + 'px';
    childDiv.style.marginTop = height * (1 - k) / 2 + 'px';
    childDiv.style.backgroundColor = getRandomColor();
    parentDiv.appendChild(childDiv);
    parentDiv = childDiv;
  }
}

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

Несколько рекурсивных вызовов

Функция может вызывать сама из себя дважды и тогда на первом шаге вызовов будет два, если на втором каждый из рекурсивных вызовов повлечёт ещё два вызова, то их вызовов будет четыре и т.д.
Сразу перейдём к визуализированному примеру. Пусть у нас опять же есть div, только квадратный и вставлять в него мы будем уже девять div’ов, причём центральный сделаем белым, затем в каждый не белый из них ещё девять с белым центральным и т.д.
html-код с css-кодом этого примера вот такой:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
<!DOCTYPE html>
<html>
<head>
<title>Recursion exaple</title>
<script type="text/javascript" src="recursion.js"></script> 
<style>
div {  
  margin: 0 auto;  
  background-color: black;
}
 
div div {
  float: left;
}
 
</style>
</head>
 
<body>
  <div style="width: 600px; height: 600px;"></div>
</body>
 
</html>

Функция, которая вставляет в родительский элемент дочерние элементы.

1
2
3
4
5
6
7
function appendChilds(parent, childs) {
  var box = document.createDocumentFragment();
  for (var i = 0; i < childs.length; i++) {
    box.appendChild(childs[i]);
  }
  parent.appendChild(box);
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function appendDivs(parentDiv, n) {
  if (n == 0) {
    return;
  }
  var width = parseInt(parentDiv.style.width),
    height = parseInt(parentDiv.style.height),
    divs = [], div;
  for (var i = 0; i < 9; i++) {
    div = document.createElement('DIV');
    div.style.width = width / 3 + 'px';
    div.style.height = height / 3 + 'px';
    divs.push(div);
  }
  divs[4].style.backgroundColor = 'white';
  appendChilds(parentDiv, divs);
  n--;
  for (var i = 0; i < divs.length; i++) {
    if (i != 4) {
      appendDivs(divs[i], n);
    }
  }  
}

Демо

Так как на каждом шаге мы делаем 8 рекурсивных вызовов, то на n-ом шаге (на нулевом у нас один div) у нас будет происходить 8n вызовов. В примере у нас n = 5, так что вызовов 85 = 215 = 32768, поэтому браузер может подвиснуть при выполнении этого примера.

Кстати, то что мы нарисовали называется ковром Серпинского. В архиве с исходными кодами есть пример, где ковёр Серпинского отрисовывается на canvas.

Количество рекурсивных вызовов может определятся динамически. Примером тому может служить конечный вариант функции ge из статьи «Три функции, упрощающие оперирование DOM-узлами». Она так же присутствует в архиве с исходными кодами.

Так же иллюстрацией работы рекурсивных функция могут служить Кривая дракона (демо), Снежинка Коха (демо)

В заключение

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

Исходники

  • Alexandr Kashuba

    Спасибо за интересную статью.