Эта статья продолжает предыдущую статью о рекурсии и примерах ее применения в программировании.
Число Фибоначчи.
Классический пример использования рекурсии. По данному целому неотрицательному числу "n" программа возвращает "n"-e число Фибоначчи.
def fib(n):
....if n == 2:
........return 1
....elif n == 1:
........return 1
....else:
........return fib(n - 1) + fib(n - 2)
n = int(input())
print(fib(n))
Первые два числа Фибоначчи равны единице. Все следующие числа в последовательности находятся по сумме двух предыдущих, поэтому функция fib запускает саму себя до тех пор, пока не дойдет до первых двух чисел, значения которых равны 1. Затем накопленный стек функций начинает закрываться в обратном порядке от первых двух чисел Фибоначчи, равных единице, до числа с номером "n".
Число сочетаний.
Что нам говорит Википедия о сочетании: "В комбинаторике сочетанием из "n" по "k" называется набор "k" элементов, выбранных из данного множества, содержащего "n" различных элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми." (источник)
def c(n, k):
....if k == 1:
........return n
....elif n == k or k == 0:
........return 1
....else:
........return c(n - 1, k) + c(n - 1, k - 1)
n = int(input())
k = int(input())
print(c(n, k))
Решение очень похоже на вычисление числа Фибоначчи, так как известно, что С(n, 1)=n и C(n, n)=1, а значит опять нужно рекурсией спустится до первых известных значений, где k=1 или k=0 или n=k, а затем вернуться к заданным значениям, вычисляя предыдущие.
Разворот последовательности.
Очень простая задача, которая отлично иллюстрирует накопление и закрытие стека рекурсивной функции. Нужно ввести последовательность целых чисел, заканчивающаяся числом 0 и вывести эту последовательность в обратном порядке, не сохраняя введенные числа ни в какие структуры (переменные, строки и т.д.)
def seq():
....n = int(input())
....if n != 0:
........seq()
........print(n)
....else:
........print(n)
seq()
Функция seq вызывает саму себя до тех пор, пока не будет введен ноль. После этого все накопленные незавершенные функции, накопленные в стеке, начнут закрываться в обратном порядке, выводя на экран введенные ранее числа.
Головоломка “Ханойские башни”.
Широко известная, в узких кругах, задача.
Головоломка “Ханойские башни” состоит из трех стержней, пронумерованных числами 1, 2, 3. На стержень 1 надета пирамидка из n дисков различного диаметра в порядке убывания диаметра (снизу находится самый большой диск, а сверху — самый маленький). Диски можно перекладывать с одного стержня на другой по одному, при этом диск нельзя класть на диск меньшего диаметра. Необходимо переложить всю пирамидку со стержня 1 на стержень 3 за минимальное число перекладываний.
Длинное условие и довольно сложный алгоритм, на первый взгляд, но программа очень компактна.
def move(n, x, y):
....if n == 1:
........print(1, x, y)
....else:
........move(n - 1, x, 6 - x - y)
........print(n, x, y)
........move(n - 1, 6 - x - y, y)
n = int(input())
move(n, 1, 3)
Нужно разбить задачу на три подзадачи:
1. переложить пирамиду дисков числом n-1 на промежуточный стержень;
2. один последний (под номером n) диск переложить на конечный стержень 3;
3. переложить пирамиду дисков числом n-1 на конечный стержень 3;
Сложность в том, что промежуточный стержень меняет свой номер, нам приходиться перекладывать пирамидки n-1 то на стержень 2, то на 3, то на 1. Например при перекладывании пирамидки из двух дисков (n=2), промежуточный стержень будет иметь номер 2, а при перекладывании пирамидки из трех дисков (n=3) сначала перекладываем пирамидку из двух на стержень 2, используя временный стержень номер 3, потом перекладываем последний диск на 3 и опять перекладываем пирамидку из двух дисков, используя стержень 1 как временный.
Как определить, какой стержень использовать как временный? У нас есть номера стержней 1, 2 и 3. В сумме это 6. Вычитая из 6 номера основных стержней, мы получим номер текущего временного (вспомогательного) стержня. Конечно номера основных стержней тоже постоянно меняются.
Заключение.
Если задачу можно разбить на повторяющиеся по смыслу подзадачи, то это верный признак того, что можно применять рекурсию, а значит существенно сократить код программы и, как часто бывает, найти единственно верное решение задачи.
