Рекурсии

Рекурсии и рекурсивные функции.

Итак, я понял, что это слово и понятие, как правило, не нравится новичкам. Предполагается, что вы понимаете некоторые основы кодирования и знаете, что такое функции/методы/подпрограммы.

Рекурсия

словарь и академическое определение:

существительное [массовое существительное] Математика и лингвистика.
Повторное применение рекурсивной процедуры или определения.

Мое представление о рекурсии:

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

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

Вот хороший пример: представьте, что перед вами поставлена задача сложить сумму 11 до 275:

0 + 11 + 22 + 33 + 44 + ... + 275

Если внимательно посмотреть на задачу, то нам нужно продолжать прибавлять 11 к результату предыдущего сложения по мере приближения к 275:
0 + 11 = 11
11 + 11 = 22
22 + 11 = 33
33 + 11 = 44
44 + 11 = 55

В коде это можно решить разными способами:

1. Самый грубый из них — просто жестко закодировать 11 + 22 … до 275 и на этом закончить. Но это будет крайне неэффективно:

// Worst solution 
var answer = 11 + 22 + 33 + 44 + 55 + 66 + 77 + 88 + 99 + 110 + 121 + 132 + 143 + 154 + 165 + 176 + 187 + 198 + 209 + 220 + 231 + 242 + 253 + 264 + 275;
console.log(answer);
// result : 3575

Есть много причин, почему это плохая идея:
i. Вы потратите много времени на написание этого
ii. ii. Это будет очень трудно поддерживать — представьте, что после всей вашей тяжелой работы требования изменились, вместо того, чтобы заканчиваться на 275, теперь вам нужно добавить до 825 или позволить пользователям добавлять любое число, которое не оставляет остатка при делении на 11.

Итеративный подход

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

function sumUp(max) {
    var answer = 0
    for (i = 0; i <= max; i += 11) {
        answer += i
    }
    return answer
}
console.log(sumUp(275))
// result : 3575

Рекурсивный подход

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

function SumUp(max) {
    // Base case
    if (max == 0) return 0;

    // Logic in its simplest form
    return max + SumUp(max - 11); 
}
console.log(SumUp(275));
// result : 3575

О, я сказал, что мы можем переписать это с меньшим количеством кода, верно? Давайте изменим функцию на стрелочную функцию, а затем используем в коде троичный оператор

const SumUp = (max) => max == 0 ? 0 :  max + SumUp(max - 11);

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

(Для гиков) То, как рекурсии работают в компьютерах, довольно интересно. У нас есть структура данных, называемая стеком вызовов, это просто стек, который хранит информацию об активных подпрограммах компьютерной программы, и он также известен как стек выполнения, Когда вызывается рекурсивная функция, функция повторно распаковывает себя в стек вызовов, пока не достигнет базового случая, что означает, что выходной результат не вычисляется сразу или до того, как все распаковки будут сделаны. После этого функции выполняются от последней вставленной функции до первой (помните, что стеки следуют LIFO Last In First Out).

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

Обратите внимание (!важно)

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

Лучший способ представить себе рекурсивную функцию — это то, что она состоит из двух частей:

1. Логика, которая решает проблему в ее простейшей форме (рекурсивная логика).

2. Базовый случай (завершающее условие, которое остановит рекурсивную функцию от вызова самой себя).

Прежде чем закончить эту статью, я хочу привести еще два примера того, где можно использовать рекурсии

Пример 1: Вычисление факториала числа:
Дайте число, например, 5. Факториал числа 5 будет результатом 5 x 4 x 3 x 2 x 1. Это можно записать с помощью рекурсии :

function factorial(number){
        // Base case
    If(number == 1){
      return number;
    }

        // Repeated steps
    Return number * factorial(number-1); 
}

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

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

//.... rest of the code
    print() {
        const printRecursively = (node) => {
            // Base case
            if (node == null) {
                return;
            }
           // Repeated Steps
            printRecursively(node.left);
            console.log(node.value);
            printRecursively(node.right);
        }
        printRecursively(this.root);
    }

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