Рекурсия в Python и практические примеры использования рекурсии

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

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

Известно, что \( n! = n \times (n-1)! \). Но как нам найти значение \( n! \) для большого \( n \)? Если бы мы знали, как вычислить \( (n-1)! \), то могли бы использовать его, поскольку \( n! = n \times (n-1)! \). Таким образом, возможно применение значения факториала меньшего числа для вычисления факториала текущего числа. Это можно реализовать в Python следующим образом:

```python

def factorial(n):

if n == 0:

return 1

else:

return n * factorial(n - 1)

```

Как это работает?

Предположим, мы вызываем функцию `factorial(4)`. Первым будет вызван `factorial(4)`, что приведет к проверки условия `if n == 0`. Поскольку условие ложно, выполнится строка `return n * factorial(n - 1)`, что означает, что будет вызвана `factorial(3)`. В памяти будут находиться две функции `factorial` — одна с параметром 4, другая с параметром 3, причем активной будет последняя.

Таким образом, функция `factorial(3)` вызовет `factorial(2)`, и так далее, пока не доберемся до `factorial(0)`, которая вернет значение 1. После этого мы будем возвращаться по стеку вызовов:

1. `factorial(1)` вернет 1 (так как `1 * 1 = 1`)
2. `factorial(2)` вернет 2 (как `2 * 1 = 2`)
3. `factorial(3)` вернет 6 (как `3 * 2 = 6`)
4. `factorial(4)` вернет 24 (как `4 * 6 = 24`)

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

Чтобы отладить программу и увидеть все функции в порядке вызова, вы можете использовать окно «Call Stack» (стек вызовов) в режиме отладки в среде Wing IDE.

Главные принципы рекурсии

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

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

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

Практические примеры рекурсии

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

Вычисление суммы натуральных чисел от 1 до n

Если \( n = 1 \), то сумма равна 1. Если \( n > 1 \), то сумма чисел от 1 до n равна сумме чисел от 1 до \( n-1 \) плюс \( n \).

```python

def sum(n):

if n == 1:

return 1

else:

return n + sum(n - 1)

```

Проверка строки на палиндромность

Крайний случай: пустая строка или строка с одним символом — палиндром.

Рекурсивный переход: строка является палиндромом, если первый и последний символы совпадают, а также строка, полученная удалением первого и последнего символа, тоже является палиндромом.

```python

def IsPalindrome(S):

if len(S) <= 1:

return True

else:

return S[0] == S[-1] and IsPalindrome(S[1:-1])

```

Суммирование элементов списка

Дан список чисел, необходимо вычислить их сумму.

Крайний случай: пустой список, сумма в котором равна 0. Если список не пустой, сумма вычисляется как сумма элементов списка без последнего элемента плюс значение последнего элемента.

```python

def Sum(A):

if len(A) == 0:

return 0

else:

return Sum(A[:-1]) + A[-1]

```

Нахождение максимального значения в списке

Дан список чисел, необходимо найти максимальное значение.

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

```python

def Max(A):

if len(A) == 1:

return A[0]

else:

return max(Max(A[:-1]), A[-1])

```

Последовательность Фибоначчи

Последовательность Фибоначчи определяется следующим образом: \( F(0) = 0 \), \( F(1) = 1 \), а любое число Фибоначчи с номером \( n \) вычисляется по формуле \( F(n) = F(n - 1) + F(n - 2) \). В случае рекурсивного вычисления чисел Фибоначчи можно аккуратно программировать эти соотношения:

```python

def Fib(n):

if n <= 1:

return n

else:

return Fib(n - 1) + Fib(n - 2)

```

Два наиболее распространенных фактора бесконечной рекурсии включают:

1. Неправильное оформление условия выхода из рекурсии. К примеру, если в программе вычисления факториала не установить проверку на \( n == 0 \), то вызов `factorial` будет непрерывным.
2. Рекурсивный вызов с некорректными параметрами. К примеру, когда функция вызывает сама себя с теми же параметрами без изменения, это также может привести к бесконечной цепочке вызовов.

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

Алгоритм быстрого возведение в степень

К числу полезных применений рекурсии относится алгоритм быстрого возведения в степень. Вычисляя степень числа с помощью простого цикла, потребуется \( n \) умножений. Тем не менее допустимо использование рекуррентных соотношений:

• \( a^n = a \cdot a^{n - 1} \), если \( n \) нечетное
• \( a^n = (a^{n // 2})^2 \), если \( n \) четное

Таким образом, алгоритм выполнит не более \( O(\log n) \) умножений:

```python

def power(a, n):

if n == 0:

return 1

elif n % 2 == 1:

return power(a, n - 1) * a

else:

return power(a, n // 2) ** 2

```

Ханойские башни

Другой классической задачей, решаемой с помощью рекурсии, является задача о Ханойских башнях. Эта головоломка состоит из трех стержней, пронумерованных 1, 2 и 3. На первом стержне стоит пирамидка из \( n \) дисков различного диаметра. Диски можно перемещать с одного стержня на другой строго по одному, при этом нельзя класть диск на меньший.

Необходимо переместить всю пирамидку со стержня 1 на стержень 3 **за минимальное количество перемещений**.

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

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

```python

def move(n, start, finish):

if n == 1:

print("Перенести диск 1 со стержня", start, "на стержень", finish)

else:

temp = 6 - start - finish # Вспомогательный стержень

move(n - 1, start, temp)

print("Перенести диск", n, "со стержня", start, "на стержень", finish)

move(n - 1, temp, finish)

```

Для решения головоломки из 10 дисков вызываем функцию так:

```python

move(10, 1, 3)

```

Оптимизация для 0 дисков

Упрощаем условие, добавив обработку нулевых дисков. Когда \( n = 0 \), ничего делать не нужно:

```python

def move(n, start, finish):

if n > 0:

temp = 6 - start - finish # Вспомогательный стержень

move(n - 1, start, temp)

print("Перенести диск", n, "со стержня", start, "на стержень", finish)

move(n - 1, temp, finish)

```

Например, чтобы установить предельное значение в 10000:

```python

import sys

sys.setrecursionlimit(10000)

```

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