Рекурсия в Python, примеры кода

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

Python поддерживает рекурсию, когда функция может вызывать саму себя. На глубину вложения рекурсивных вызовов наложены ограничения. По умолчанию Python прерывает рекурсию и бросает исключение RecursionError, если обнаруживает, что глубина стека рекурсивных вызовов превысила 1000. Для этого предела можно установить другое значение с помощью функции setrecursionlimit() модуля sys.

Однако возможность изменения рекурсивного предела не означает, что вы можете сделать его сколько угодно большим. Абсолютное максимальное значение этого предела зависит от платформы, на которой выполняется программа. Максимальное значение рекурсивных вызовов можно посмотреть с помощью sys.getrecursionlimit(). В типичных случаях вы можете рассчитывать на рекурсию глубиной порядка нескольких тысяч уровней. При чрезмерно большой установленной глубине рекурсивных вызовов программа может завершиться аварийно. Такие выходящие из-под контроля рекурсии, являются одной из немногих причин возможного краха программы на Python, когда не срабатывает даже обычный защитный механизм исключений Python. Поэтому "НЕ ЛЕЧИТЕ" программу, в которой возникает исключение RecursionError, путем повышения разрешенной глубины вложения рекурсивных вызовов с помощью функции sys.setrecursionlimit(n). В таких случаях лучше изменить организацию программы таким образом, чтобы избавиться от рекурсии или хотя бы постараться уменьшить глубину вложения рекурсивных вызовов.

Рекурсию в Python рассмотрим на примере решения факториала, функции, определённой на множестве неотрицательных целых чисел. Например 5! = 1 * 2 * 3 * 4 * 5 = 120

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

x = factorial(5)
print(x)
# 120

Наглядный пример работы рекурсии:

def countDown(start, indent=0):
    print('-'*indent, '>', start)
    start = start - 1
    indent = indent + 1
    if start >= 0:
        # Рекурсивный вызов 'countDown', в которой 
        # происходит печать строки, но только уже с 
        # другими значениями, которые вычисляются выше
        countDown(start, indent)

countDown(5, 2)
# -- > 5
# --- > 4
# ---- > 3
# ----- > 2
# ------ > 1
# ------- > 0

Еще нагляднее:

def countDown(start, indent=1):
    print('-'*indent, 'UP:', start)
    if start == 0:
        # Здесь рекурсивный вызов 'countDown' прекратился, сначала 
        #  печатается эта строчка, потом все, что было накоплено в стеке...
        print('-'*indent, 'DOWN:', start)
    else:
        # Рекурсивный вызов 'countDown'
        countDown(start - 1, indent + 1)
        # Вызов 'countDown' не дает функции print выполнится 
        # и накапливает (откладывает) ее исполнение в стеке
        print('-'*indent, 'DOWN:', start)

countDown(5)
# - UP: 5
# -- UP: 4
# --- UP: 3
# ---- UP: 2
# ----- UP: 1
# ------ UP: 0
# ------ DOWN: 0
# ----- DOWN: 1
# ---- DOWN: 2
# --- DOWN: 3
# -- DOWN: 4
# - DOWN: 5