Рекурсивная функция в Python и простые примеры

В этом уроке вы узнаете о рекурсивных функциях Python и о том, как их использовать для упрощения программного кода на практических примерах.

Содержание

Что такое рекурсивная функция в Python?
Примеры рекурсивных функций Python
1) Простой пример рекурсивной функции в Python
2) Вычисление суммы последовательности с помощью рекурсивной функции

Что такое рекурсивная функция в Python?

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

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

def fn():
    # ...
    fn()
    # ...

В функции fn() #… означает другой код.

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

def fn():
    # ...
    if condition:
        # stop calling itself
    else:
        fn()
    # ...

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

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

Примеры рекурсивных функций Python

Давайте рассмотрим несколько примеров использования рекурсивных функций в Python.

1) Простой пример рекурсивной функции в Python

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

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

3
2
1

Ниже определяется функция count_down():

def count_down(start):
    """ Count down from a number  """
    print(start)

Если вы сейчас вызовете функцию count_down():

count_down(3)

…она покажет только цифру 3.

Чтобы показать цифры 3, 2 и 1, нужно:

Сначала вызвать count_down(3), чтобы отобразить число 3.
Во-вторых, вызвать count_down(2), чтобы отобразить число 2.
Наконец, вызовите count_down(1), чтобы отобразить число 1.

Для этого внутри функции count_down() вам необходимо определить логику для вызова функции count_down() с аргументами 2 и 1, т.е. сделать функцию count_down() рекурсивной.

Следующий код определяет рекурсивную функцию count_down() и вызывает ее, передавая число 3:

def count_down(start):
    """ Count down from a number  """
    print(start)
    count_down(start-1)


count_down(3)

Если вы запустите программу, вы увидите следующую ошибку:

RecursionError: maximum recursion depth exceeded while calling a Python object

Причина в том, что функция count_down() вызывает себя бесконечно, пока система не остановит ее.

Поскольку вам нужно прекратить обратный отсчет, число достигнет нуля. Для этого вы добавляете такое условие:

def count_down(start):
    """ Count down from a number  """
    print(start)

    # call the count_down if the next
    # number is greater than 0
    next = start - 1
    if next > 0:
        count_down(next)


count_down(3)

Выход:

3
2
1

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

2) Вычисление суммы последовательности с помощью рекурсивной функции

Предположим, вам нужно вычислить сумму последовательности, например, от 1 до 100. Простой способ сделать это — использовать цикл for с функцией range():

def sum(n):
    total = 0
    for index in range(n+1):
        total += index

    return total


result = sum(100)
print(result)

Выход:

Чтобы применить технику рекурсии, вы можете вычислить сумму последовательности от 1 до n следующим образом:

сумма(п) = п + сумма(п-1)
сумма(n-1) = n-1 + сумма(n-2)
…
сумма(0) = 0

Функция sum() продолжает вызывать сама себя до тех пор, пока ее аргумент больше нуля.

Следующий код определяет рекурсивную версию функции sum():

def sum(n):
    if n > 0:
        return n + sum(n-1)
    return 0


result = sum(100)
print(result)

Как видите, рекурсивная функция намного короче и читабельнее.

Если вы используете тернарный оператор, sum() будет еще более кратким:

def sum(n):
    return n + sum(n-1) if n > 0 else 0


result = sum(100)
print(result)