Дейкстра был прав — рекурсия не должна быть сложной

Почти в каждом языке программирования есть управляющие конструкции вроде блоков if…else/switch…case и итеративные конструкции вроде циклов for и while. Большинство начинающих программистов сначала изучают именно итеративные конструкции.

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

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

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

Зачем нужна рекурсия?

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

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

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

Разберём пример. Допустим, вы хотите вычислить сумму всех элементов массива, в котором есть вложенные подмассивы. Так, чтобы при получении вот таких вложенных массивов:

[1,[11,42,[8, 1], 4, [22,21]]]

функция возвращала сумму всех элементов:

1+11+42+8+1+4+22+21 = 110.

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

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

function sum(a) {
    let result = 0;

    for (let i = 0; i < a.length; i++) {
        result += a[i];
    }
    return result;
}

assert.equal(sum([1, -5, 100]), 96);

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

function sum(a) {
    let result = 0;

    for (let i = 0; i < a.length; i++) {
        if (Array.isArray(a[i])) {
            result += sum(a[i])
        } else {
            result += a[i];
        }
    }
    return result;
}

assert.equal(sum([1,[11,42,[8, 1], 4, [22,21]]]), 110);

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

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

  1. Если текущий шаг алгоритма является решением задачи — вернуть результат.
  2. Если текущий шаг не решение — посмотреть, куда отсюда ещё можно пойти.
  3. Если есть куда идти — выбрать вариант и пойти туда, чтобы проверить, не решение ли это.
  4. Если идти больше некуда — вернуться назад.

Разберём пример. Дано следующее дерево:

Оно представлено узлами с потомками:

let tree = {
    name: 'A',
    value: 4,
    children: [
        {
            name: 'B', value: 7,
            children: [{name: 'C', value: 9, children: []}]
        },
        {
            name: 'D', value: 11,
            children: [{name: 'E', value: 9, children: []}]
        },
        {name: 'F', value: 55, children: []},
        {
            name: 'G', value: 65,
            children: [
                {name: 'H', value: 21, children: []},
                {name: 'I', value: 33, children: []}
            ]
        }
    ]
};

А задача — найти узел со значением 21.

Действовать будем так:

  1. Сначала проверяем узел A.
  2. Если это не то, что мы ищем, идём в B, затем в C.
  3. Ни один узел на нашем пути не подходит, и идти отсюда некуда, поэтому мы возвращаемся к A.
  4. Затем проверяем D и E. Не повезло.
  5. Возврат. F.
  6. Снова возврат. Проверяем G. И опять мимо.

Но нам ещё есть куда идти. Наконец H. Это тот узел, который мы искали.

А вот простая реализация:

function find(node, value) {
    if (node.value === value) {
        return node;
    } else {
        for (let i = 0; i < node.children.length; i++) {
            let found = find(node.children[i], value);
            if (found !== null) {
                return found;
            }
        }

        return null;
    }
}

assert.equal(find(tree, 21).name, 'H');

Проектирование решения

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

if (Array.isArray(a[i])) {
    result += sum(a[i])

не думайте о том, что произойдёт при выполнении функции sum. Это неудачный способ думать о рекурсии. Вместо этого доверьтесь тому, что она вернёт правильную сумму всех элементов массива a[i]. И ещё: не воспринимайте рекурсивную программу как последовательность шагов выполнения и не пытайтесь восстановить дерево выполнения в голове. Для некоторых сложных задач это будет очень трудно и не поможет вам прийти к решению.

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

Найдя более простую задачу, переходите к поиску самой простой задачи, которую вашей функции придётся решить. Эта простейшая задача называется базовым случаем. Обычно он выражается в виде условия, которое завершает рекурсию. В наших предыдущих примерах он принимает форму цикла for, проверяющего, остались ли элементы в массиве (sum) или потомки у узла (find). Иногда в лёгких задачах та более простая задача, которая помогает решить исходную, и есть базовый случай. Но с более трудными задачами это не так — например, со знаменитой задачей о Ханойской башне:

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

Более простая задача, которую здесь нужно разглядеть, такова:

  1. Переместить n-1 дисков на вспомогательный стержень.

  1. Переместить последний диск с исходного стержня на целевой.

  1. После того как последний диск перемещён, оставшиеся диски со вспомогательного стержня можно переложить на целевой.

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

function move(n, src, aux, dest) {

    // перекладываем все диски, кроме последнего, с исходного
    // на вспомогательный стержень; именно поэтому в вызове функции
    // стержни aux и dest меняются местами, чтобы aux стал целевым
    move(n - 1, src, dest, aux);

    // перекладываем последний диск с исходного стержня на целевой
    dest.push(src.pop());

    // перекладываем оставшиеся диски со вспомогательного стержня
    // на целевой; именно поэтому в вызове функции стержни aux и src
    // меняются местами, чтобы вспомогательный стал исходным
    move(n - 1, aux, src, dest);
}

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

Если остался один диск — просто переложите его на целевой стержень:

function move(n, src, aux, dest) {
    if (n === 1) {
        dest.push(src.pop());
    } else {
        move(n - 1, src, dest, aux);
        dest.push(src.pop());
        move(n - 1, aux, src, dest);
    }
}

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

Теперь попробуйте применить изученное к следующим задачам:

  1. Поиск суммы вложенных массивов

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

  1. Генерация двоичных строк

Напишите функцию, которая генерирует все возможные комбинации 1 и 0 для n битов. Например, если функция получает 2 в качестве количества битов, она должна выдать следующие 4 комбинации: 00,01,10,11. Использовать математические операторы нельзя.

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

Решения и пояснения — в конце статьи.

Оптимизация хвостовых вызовов

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

function a(n) {
    let a = 1;
    return a + n;
}

function b(n) {
    let b = 5;
    let value = a(n);  // строка B
    return b + value;
}

function c() {
    let c = 3;
    let v = b(c);  // строка C
    console.log(v);
}

c();  // строка A

и вы поставите точку останова внутри a, стек вызовов будет выглядеть примерно так:

a() (return to: {b(): B}, locals: {a=1, n=3})
b() (return to: {c(): C}, locals: {b=5, n=3})
c() (return to: {index.js: A}, locals: {c=3, v=undefined})

Он говорит, что функция a была вызвана из b, а b — из c. Отсюда и название «стек вызовов» — стопка вызовов функций. Каждая запись в стеке называется кадром стека (stack frame) и хранит, помимо прочего, следующее: локальные переменные и адрес возврата (куда вернуться, когда текущая функция завершится). Важно, что количество и размер кадров в стеке ограничены. Это значит, что если продолжать вызывать функции достаточно долго, вы получите ошибку переполнения стека. Этот предел не фиксирован, различается от среды к среде и зависит от размера кадра каждой конкретной функции.

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

function fact(n) {
    if (n === 0 || n === 1) {
        return 1;
    }
    return n * fact(n - 1);
}

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

Тем не менее для многих функциональных языков вроде Lisp и Scheme это предпочтительное решение. Как же они избегают упомянутых проблем? Ответ — оптимизация хвостовых вызовов. Взглянем на переработанный код примера со стеком, приведённого выше:

function a(n, p) {
    let a = 1;
    return a + n + p;
}

function b(n) {
    let b = 5;
    return a(n, b);
}

function c() {
    let c = 3;
    let v = b(c);  // строка C
    console.log(v);
}

c();  // строка A

Теперь кажется, что создавать кадр стека для функции b бессмысленно: всё, что она делает, — вызывает a и после этого не выполняет никаких действий. Компилятор это замечает и оптимизирует такие вызовы, не создавая кадр стека для b. Оптимизированный стек теперь выглядит так:

a() (return to: {c(): C}, locals: {a=1, n=3, p=5})
c() (return to: {index.js: A}, locals: {c=3, v=undefined})

Посмотрите на разницу в функции b до и после переработки:

// без оптимизации хвостовых вызовов
let value = a(n);
return b + value;

// с оптимизацией хвостовых вызовов
return a(n, b);

Итак, главное отличие в том, что после возврата функции a никаких действий больше нет. Перепишем нашу функцию факториала так, чтобы она подходила под оптимизацию хвостовых вызовов:

function fact(acc, n) {
    if (n === 1) {
        return acc;
    } else {
        return fact(acc * n, n - 1);
    }
}

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

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

В некоторых функциональных языках оптимизации хвостовых вызовов можно добиться и через стиль передачи продолжений (CPS) — то есть через колбэки. При использовании колбэков операторы return не нужны, и компилятор может оптимизировать рекурсивные вызовы. Хотя JavaScript очень хорошо поддерживает модель колбэков, оптимизацию хвостовых вызовов через CPS он сейчас не поддерживает.

Решения

Итак, первая задача:

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

Начать можно с поиска более простой задачи — это массив без вложенных подмассивов. Зададим те же вопросы, чтобы решить эту более простую задачу:

  1. Какая задача проще? Более простая задача — когда у меня есть сумма n-1 элементов и нужно лишь прибавить к ней текущий элемент.
  2. Какой случай самый простой? Самый простой случай — когда прибавлять больше нечего: возвращаем 0.

Вот реализация:

function sum(a, i) {
    if (i < 0) {
        return 0;
    } else {
        return a[i] + sum(a, i - 1);
    }
}

let input = [1, 2, 0, 3];
assert.equal(sum(input, input.length - 1), 6);

Итак, мы решили более простую задачу без вложенных массивов. Теперь нужно учесть вложенные массивы. Нужно проверить, является ли элемент массивом, и если да — просто запустить для него функцию sum. Важно не забыть получить сумму элементов вложенного подмассива и прибавить её к итоговому значению. Вот окончательная реализация:

function sum(a, i) {
    if (i < 0) {
        return 0;
    }

    let current = a[i];

    if (Array.isArray(a[i])) {
        current = sum(a[i], a[i].length - 1);
    }

    return current + sum(a, i - 1);
}

let input = [1, 2, [1, 2], 3, [5]];
assert.equal(sum(input, input.length - 1), 14);

Теперь разберём вторую задачу:

Напишите функцию, которая генерирует все возможные комбинации 1 и 0 для n битов. Например, если функция получает 2 в качестве количества битов, она должна выдать следующие 4 комбинации: 00,01,10,11. Использовать математические операторы нельзя.

Какой здесь самый простой случай? Нужно получить строки всего для одного бита. Для этого у нас будет две строки: 1 и 0. Значит, у нас есть функция, которая выводит 1 и 0, если количество битов равно 1. Запишем её, предполагая, что есть глобальная переменная a, содержащая массив:

function binary(n) {
    if (n === 1) {

        a[n - 1] = 0;
        console.log(a.join(''));

        a[n - 1] = 1;
        console.log(a.join(''));
    }
}

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

function binary(i) {
    if (i === 0) {
        console.log(a.join(''));
    } else {
        a[i - 1] = 0;
        binary(i - 1);
        a[i - 1] = 1;
        binary(i - 1);
    }
}

Теперь посмотрим, какие комбинации получатся для 2 битов.

Итак, начинаем с того, что ни один бит не установлен. Затем устанавливаем бит n в 0. Затем делаем то же самое для бита n-1. Мы следуем этой схеме, пока не останется битов для установки. Печатаем комбинацию и возвращаемся на уровень выше. Затем устанавливаем бит n в 1. Понятно, что на каждом шаге функция занимается лишь установкой текущего бита и вызовом функции для обработки оставшихся битов.

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