Почему я должен использовать рекурсию?

Рекурсия против итерации - одна из тех давних священных войн программирования, которая разделяет сообщество разработчиков почти так же, как Vim / Emacs, Tabs / Spaces или Mac / Windows. На самом деле нет правильного ответа, любой алгоритм, который можно реализовать с помощью итерации, можно реализовать с помощью рекурсии и наоборот. Рекурсивные решения и итерационные решения могут различаться с точки зрения памяти, временной сложности или удобочитаемости, но, тем не менее, любая проблема, которую можно решить с помощью одного, может быть решена с помощью другого. Для тех, кто не знаком, итерация относится к процедурному пошаговому процессу прохождения перечислимого набора сущностей и выполнения некоторой операции на каждой итерации. Напротив, рекурсия относится к разбиению проблемы на несколько более мелких и простых подзадач, которые можно использовать для решения общей проблемы. Я ни в коем случае не рекомендую выбирать рекурсивное решение во всех случаях. Часто выбор итеративного подхода будет проще, более производительным или более читаемым. Однако существует множество вариантов использования и структур данных, которые поддаются рекурсивным решениям. В следующей статье мы обсудим несколько различных подходов к разработке рекурсивных решений.

1. Преодолеть бесконечную петлю

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

// This will create an infinite loop (lang = TypeScript)
const reverseList = (list: Array<number>): Array<number> => {
    return reverseList(list); // This is the recursive call
}

Чтобы избежать этого, рекурсивные функции обычно имеют так называемый базовый случай, который часто выполняется перед рекурсивным вызовом, чтобы он мог проверять какое-либо условие на основе предположительно измененные параметры функции, переданные этому конкретному экземпляру функции. В большинстве случаев базовым случаем будет пустой список / массив, null, 0, пустая строка или что-то еще, указывающее на конец выполнения этой функции. В нашем примере выше reverseList принимает массив и возвращает массив; стандартным базовым случаем будет проверка того, что список пуст. Теперь наш пример функции reverseList становится следующим:

// This will still create an infinite loop (lang = TypeScript)
const reverseList = (list: Array<number>): Array<number> => {
    // Base Case
    if (list.length === 0) {
        return list;
    }
    return reverseList(list); // This is the recursive call
}

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

const reverseList = (list: Array<number>): Array<number> => {
    if (list.length === 0) {
        return list;
    }
    // This removes and returns 1 element starting at index 0
    let first : Array<number> = list.splice(0, 1);
    // List had its first element removed before recursive call
    return reverseList(list).concat(first);
}

Для тех из вас, кто предпочитает не деструктивно изменять входной массив, вы можете рассмотреть возможность создания копии массива с помощью slice вместо splice. Наша окончательная версия reversList теперь выглядит так.

const reverseList = (list: Array<number>): Array<number> => {
    if (list.length === 0) {
        return list;
    }
    // This returns a new array only containing first element
    let first : Array<number> = list.slice(0, 1);
    // Create a new slice of the list without the first
    return reverseList(list.slice(1, list.length)).concat(first);
}

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

2. Доверьтесь рекурсии

Мне потребовалось много времени, чтобы понять, когда я впервые научился программировать, но я искренне верю, что это может быть самая важная часть для понимания красоты рекурсии. По сути, рекурсивное решение разбивает проблему на последовательно меньшие подзадачи, пока мы не дойдем до тривиальной подзадачи (базовый случай). Если мы посмотрим на наш предыдущий пример и прочитаем наш код с примером input [1, 2, 3], функция будет выглядеть следующим образом: Добавить первый элемент в конец перевернутого списка всех элементов после первого. Если мы «доверяем рекурсии», тогда мы верим, что вызов reverseList с [2, 3] просто сработает, и тогда все, о чем нам нужно думать, это как настроить решение. к подзадаче, чтобы соответствовать решению общей проблемы. В этом случае это довольно просто: решение подзадачи [2, 3] есть [3, 2], поэтому все, что нам нужно сделать, это добавить первый элемент в конец решения подзадачи, и у нас есть решение общая проблема. Это читается точно так же, как наше рекурсивное решение: добавить текущий элемент на оборотную сторону списка без текущего элемента. В конце концов, выполнение заканчивается на базовом случае, который возвращает пустой список, который всплывает до всех предыдущих вызовов reverseList. Визуально это выглядело бы так:

reverseList([1, 2, 3]) →
reverseList([2,3]) + 1 → 
reverseList([3]) + 1 + 2 →
reverseList([]) + 1 + 2 + 3 →
[]+1+2+3 →
[1,2,3]

Дело в том, что вместо того, чтобы перебирать нашу структуру данных и выполнять некоторые операции на каждом шаге, мы можем преобразовать нашу структуру данных более декларативным образом. Решение читается как более прямое отображение входных данных в выходные данные. В итеративном решении это будет больше рассматриваться как процедурный список указаний о том, как построить вывод с нуля на основе ввода. Как правило, итеративное решение предоставляет более подробную информацию о том, как создается решение, но более непрозрачно с точки зрения того, как входные данные сопоставляются с выходными. Напротив, рекурсивное решение обеспечивает более прямое, удобочитаемое и функциональное сопоставление ввода с выводом, однако оно может быть более непрозрачным с точки зрения того, как был сгенерирован вывод. . Функция ниже демонстрирует итеративный подход к reverseList, поскольку вы можете видеть, что это больше похоже на описание шагов, которые необходимо предпринять для создания нового списка, а не на преобразование одного списка в другой.

const reverseList = (list: Array<number>): Array<number> => {
    let result : Array<number> = [];
for (let i : number = list.length - 1; i >= 0; i--) {
         result.push(list[i]);
    }
    return result;
}

Причина, по которой имеет значение то, как определенный фрагмент кода «читает», заключается в том, что программирование не говорит компьютеру, что делать, а скорее выражает другим людям, что компьютер должен делать.

3. Рекурсивные алгоритмы ❤️.

Некоторые структуры данных рекурсивны по своей природе. Деревья, связанные списки и даже DOM - все это рекурсивные структуры данных. Все это означает, что все эти структуры данных содержат самореференциальные поля. Узел в дереве имеет потомков, которые сами являются деревьями. Узел в связанном списке указывает на другие узлы, которые сами являются связанными списками. Элемент DOM указывает на… вы поняли. Поскольку все эти структуры данных среди прочих являются рекурсивными, имеет смысл только то, что алгоритмы, работающие с этими структурами данных, предоставляют рекурсивные решения. Один из моих любимых примеров - очень простой алгоритм, который проверяет, действительно ли двоичное дерево является «двоичным деревом поиска», которое является особым типом двоичного дерева, которое удовлетворяет ограничению, согласно которому для каждого узла в дереве значение узла меньше или равно значению левого узла. и значение узла больше или равно значению правого узла.

const isBinarySearchTree = (node) : boolean => {
    if (node == null) {
        return true;
    }
    if (node.left != null && node.left.value > node.value) {
         return false;
    }
    if (node.right != null && node.right.value < node.value) {
        return false;
    }
    if (!isBinarySearchTree(node.left) ||  
        || !isBinarySearchTree(node.right)) {
        return false;
    }
    return true;
}

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

Удачи в ваших рекурсивных приключениях!