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

Звучит немного запутанно, верно? Может быть! Рекурсия — одна из тех концепций программирования, в которых мне определенно потребовалось некоторое время, чтобы понять, когда я только начинал. Но давайте попробуем упростить приведенное выше определение на примере.

Допустим, мы хотели написать на питоне функцию, которая будет вычислять факториал числа. Если вы раньше не встречались с факториалами, факториал — это функция, которая определена для положительного целого числа «n» как произведение всех положительных целых чисел от 1 до n и обозначается символом !

Чтобы написать итеративную функцию, которая делает это, мы можем использовать цикл while.

def factorial(n):
    if n < 0:
        return None
    elif n == 0:
        return 1
    else:
        result = 1
        while n > 0:
            result *= n
            n -= 1
        return result

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

Чтобы понять, что значит сказать, что факториал может быть определен рекурсивно, мы можем взглянуть на приведенный выше пример 5! и рассмотрим определение 4!

В дополнении 4! мы можем заметить, что 4x3x2x1 также находится в расширении 5!

Это позволяет нам выразить 5! в плане 4!

Этот шаблон позволяет написать факториал как сам раз (сам по себе — 1)! помогает нам написать гораздо более простую функцию.

def factorial(n):
    if n < 0:
        return None
    elif n == 0:
        return 1
    else:
        return n * factorial(n-1)

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

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

def factorial(n):
    if n < 0:
        return None
    elif n == 0:
        return 1
    else:
        return n * factorial_n_minus_1(n-1)

def factorial_n_minus_1(some_number):
  # Don't worry about it, this function definitely works

В приведенном выше примере у нас есть новая волшебная функция, которая поможет нам подумать о том, как написать рекурсивный код для факториала. Как всегда, у нас те же ограничения, но вместо того, чтобы называть себя функцией факториала, мы можем представить, что у нас есть другая функция, factorial_n_minus_1, которая способна вычислить факториал n-1, но по какой-то причине не может вычислить n. !, то все, что нам нужно сделать, это написать функцию, которая использует эту волшебную функцию для правильного вычисления n!

Как только мы это сделаем, мы можем заменить вызов нашей волшебной функции вызовом нашей собственной функции, и вуаля! Работающая рекурсивная функция!

Я надеюсь, что эта статья была полезной! Если у вас есть вопросы, комментарии или предложения по написанию лучших статей, оставляйте их в комментариях!