Что такое рекурсия?

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

Рекурсивная функция - это функция, которая либо вызывает себя, либо находится в потенциальном цикле вызовов функций. Как указано в определении, существует два типа рекурсивных функций.

  • Линейная рекурсия:

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

  • Множественная рекурсия:

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

Рассмотрим функцию, которая вызывает сама себя: мы называем этот тип рекурсии линейной рекурсией. - Кредит

По сути, рекурсия решает проблему, разбивая ее на более мелкие части.

Написание рекурсивных функций

Рекурсивная функция имеет следующую общую форму (это просто спецификация общей функции, которую мы видели много раз):

function factorial(number) {
    if (number === 1) {
        return 1;
    }
    return number * factorial(number - 1);
}

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

Выше представлены две функции Python, использующие концепцию рекурсии. Первый, который возвращает результат числа a, возведенного в степень второго целого числа b. Строки 2 и 4 оператора определяют простой случай, который возвращает простое значение для пользователя, а также может использоваться для выхода из цикла. Например, если мы хотим вычислить степень двойки в степени 3 с помощью нашей функции: power(2,3).

Первое и второе условия (строки 2 и 4) оцениваются как false, когда он переходит к оператору else на line 6, он начинает рекурсию и начинает с возврата результата, который вызывает саму функцию:

power(2,3) = 2 * power(2,(3-1=2)) = 2 * power(2,2)

В новом вызове функции обе строки 2 и 4 снова оцениваются как false, а затем функция снова вызывает себя.

power(2,2) = 2 * power(2, (2-1=1)) = 2 * power(2,1)

Здесь мы разбили исходную задачу на две части:

power(2,3) = 2 * power(2,2)

Начиная с power(2,2) evaluates to 2 * power(2, 1), мы можем переопределить формулировку проблемы гораздо проще:

power(2,3) = 2 * (2 * power(2,1)

При вызове новой функции power(2,1) строки 2 и 4 также не оцениваются как True, поэтому нам нужно вызвать функцию в третий раз. На этот раз power(2,1) оценивается как:

power(2,1) = (2 * power(2,1-1) = 2 * power(2,0)

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

Таким образом, мы можем упроститьpower(2,3) до

2 * (2 * (2 * power(2,0)))

Эту проблему легко решить, потому что line 2 теперь оценивается как True.

Это означает, что power(2,0) == 1. Теперь у нас есть утверждение, которое выглядит так power(2,3) = 2 * (2 * (2 * 1)) = 8.

Потрясающий материал! Мы разобрали нашу проблему и при этом решили ее.

Это recursion разбито на простые блоки. Эквивалент javascript указанной выше функции python показан ниже:

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

Вперед, разработчики!