Функциональное программирование с точки зрения EcmaScript. Рекурсия и её виды

Привет, Хабр!

Сегодня мы продолжим наши изыскания на тему функционального программирования в разрезе EcmaScript, на спецификации которого основан JavaScript. В предыдущих статьях цикла были рассмотрены следующие темы:

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

Рекурсия

Как всегда, википедия помогает нам с поиском определения:

Реку́рсия — определение, описание, изображение какого-либо объекта или процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя. Термин «рекурсия» используется в различных специальных областях знаний — от лингвистики до логики, но наиболее применение находит в математике и информатике.

Применительно к программированию под рекурсией подразумевают процессы, которые вызывают сами себя в своём теле. Рекурсивная функция имеет несколько обязательных составляющих:

• Терминальное условие — условие прекращения выполнения
• Правило по которому осуществляется движение в глубь по рекурсии

Рассмотрим самый популярный пример рекурсии — вычисление факториала.

const factorial = (n) => {
  if (n === 0) {
    return 1;
  }

  return n * factorial(n - 1);
}

Выделим характерные составляющие рекурсивной функции. Терминальное условие

  if (n === 0) {
    return 1;
  }

и правило движения по рекурсии

return n * factorial(n - 1);

Важно осознавать, что рекурсия это не какая-то специфическая фича JS, а техника очень распространённая в программировании.

Рекурсивный и итеративный процессы

Рекурсию можно организовать двумя способами: через рекурсивный процесс или через итеративный.

Рекурсивный процесс мы с вами уже видели:

const factorial = (n) => {
  if (n === 0) {
    return 1;
  }

  return n * factorial(n - 1);
}

Итеративное решение задачи о факториале выглядело бы так:

const factorial = (n) => {
  const iter = (counter, acc) => {
    if (counter === 1) {
      return acc;
    }
    return iter(counter - 1, counter * acc);
  };

  return iter(n, 1);
};

Оба этих варианта это рекурсия. В обоих решениях есть характерные для рекурсии черты: терминальное условие и правило движения по рекурсии. Давайте разберём их отличия.

Рекурсивный процесс на каждом шаге запоминает действие. которое надо сделать. Дойдя до термального условия, он выполняет все запомненные действия в обратном порядке. Поясним на примере. Когда рекурсивный процесс считает факториал 6, то ему нужно запомнить 5 чисел чтобы посчитать их в самом конце, когда уже никуда не деться и рекурсивно двигаться вглубь больше нельзя. Когда мы находимся в очередном вызове функции, то где-то снаружи этого вызова в памяти хранятся эти запомненные числа.

Выглядит это примерно так:

factorial(3);        //для 6ти писать много, поэтому ограничусь факториалом 3ки
3 * factorial(2);       
3 * 2 * factorial(1);  
3 * 2 * 1;              
3 * 2;
6;

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

Думаю, вы помните, что в первой статье из цикла о Функциональном программировании мы говорили о важности имутабельности и отсутствия состояния. Наличие состояния порождает много проблем, с которыми не всегда легко справится.

Итеративный процесс отличается от рекурсивного фиксированным количеством состояний. На каждом своём шаге итеративный процесс считает всё, что может посчитать, поэтому каждый шаг рекурсии существует независимо от предыдущего.

Выглядит это так:

iter(3, 1); // iter(3 - 1, 1 * 3); //обратите внимание, что тут мы записали факториал 6ти, 
iter(2, 3); // iter(2 - 1, 2 * 3);//но количество строк меньше, чем в предыдущем примере для 3ки
iter(1, 6); // counter === 1, return 6
6;

Думаю, очевидно, что итеративный процесс потребляет меньше памяти. Следовательно, всегда при создании рекурсии следует использовать его. Единственное исключение: если мы не можем посчитать значение до достижения термального условия.

Древовидная рекурсия

Многие считают, что деревья и работа с ними это что-то очень заумное, сложное и не понятное простым смертным. На самом деле это не так. Любая иерархическая структура может быть представлена в виде дерева. Даже человеческое мышление подобно дереву.

Чтобы лучше понять древовидную рекурсию разберём простой и популярный пример — числа Фибоначчи.

Чи́сла Фибона́ччи — элементы числовой последовательности 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, … (последовательность A000045 в OEIS), в которой первые два числа равны либо 1 и 1, либо 0 и 1, а каждое последующее число равно сумме двух предыдущих чисел. Названы в честь средневекового математика Леонардо Пизанского (известного как Фибоначчи).

Математически довольно просто сформулировать описание (а ведь декларативное программирование и есть описание) данной последовательности:

fib(n) = [
равно 0 если n = 0,//(1)
равно 1 если n = 1,//(2)
fib(n-1) + fib(n-2) во всех остальных случаях
]

Теперь давайте перейдём от математики к логическим рассуждениям(нам ведь нужно программную логику написать). Для вычисления fib(5) нам придётся вычислить fib(4) и fib(3). Для вычисления fib(4) нам придётся вычислить fib(3) и fib(2). Для вычисления fib(3) нам придётся вычислить fib(2) и так до тех пор пока мы не дойдём до известных значений (1) и (2) в нашей математической модели.

На какие мысли нас должны навести наши рассуждения? Очевидно, мы должны использовать рекурсию. Термальное условие можно сформулировать как n <= 1. Однако, вместо одной ветви рекурсии(как в предыдущих примерах) у нас будет две ветви: fib(n-1), fib(n-2).

const fib = (n) => (n <= 1 ? n : fib(n - 1) + fib(n - 2));

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

Заключение

Рекурсия является очень мощным средством программирования. Напомню, что, как правило, мы используем итеративный процесс. Использовать рекурсивный процесс стоит только в том случаем если мы не можем посчитать промежуточный результат на каждом шаге рекурсии.