Понятие очень простое и в тоже время вызывающее массу проблем в понимании. Тем же кто освоил данный инструмент открывается новый и загадочный для многих мир лаконичных и красивых программных решений.
Предлагаю вашему вниманию примеры программ с использованием рекурсии для понимания механизма работы данного явления.
Рекурсия в программировании - это когда часть программы использует саму себя для выполнения однотипных вычислений несколько (возможно очень много) раз. То есть вы можете воспользоваться уже написанным вами кодом снова и снова, что является достоинством этого подхода, так как разбивает сложную задачу на мелкие и однотипные подзадачи. Опасность кроется в возможности неконтролируемой зацикленности вызовов и погружение в глубины повторяющихся вычислений, пока переполнение оперативной памяти не прекратит это безумие.
Приведу несколько простых примеров использования рекурсии в мирных целях.
Сложение без сложения.
Можно сложить два целых и неотрицательных числа "a" и "b" без использования арифметических операций, кроме двух: +1 и -1.
def sum(a, b):
....if b != 0:
........a += 1
........b -= 1
........sum(a, b)
....else:
........print(a)
a = int(input())
b = int(input())
sum(a, b)
Функция sum добавляет при каждом вызове единицу к "a" и вычитает единицу из "b" и вызывает саму себя до тех пор, пока "b" не станет равно нулю.
Возведение в степень.
Чтобы возвести число "a" в степень "n", нужно умножить число "a" само на себя "n" раз.
def power(a, n):
....global s
....if nn > 0:
........s = s * a
........nn -= 1
........power(a, n)
....else:
........print(s)
a = float(input())
n = int(input())
s = 1
power(a, n)
Функция power умножает переменную "s" на число "а" и вызывает саму себя "n" раз. Тот же метод используется при возведении числа в отрицательную степень, с той только разницей, что в конце ответом будет единица, деленная на полученное число "s".
Быстрое возведение в степень.
Для ускорения работы программы возведения в степень (ну и просто поумничать) воспользуемся алгоритмом быстрого возведения "a" в степень "n": aⁿ = (a²)ⁿ/² при четном "n", aⁿ=a⋅aⁿ⁻¹ при нечетном "n".
def power(a, n):
....global s
....if n == 1:
........print(s * a)
....elif n % 2 == 0:
........power(a * a, n / 2)
....else:
........s = s * a
........power(a, n - 1)
a = float(input())
n = int(input())
s = 1
if n == 0:
....print(1)
else:
....power(a, n)
Функция power запускает саму себя только один раз с разными параметрами, в зависимости от того, является ли "n" четным или нечетным.
Алгоритм Евклида.
Алгоритм Евклида – это алгоритм нахождения наибольшего общего делителя (НОД) пары целых чисел. Наибольший общий делитель (НОД) – это число, которое делит без остатка два числа и делится само без остатка на любой другой делитель данных двух чисел.
Для программирования этой задачи, лучше всего использовать блок-схему вычисления.
Реализация на языке Python такова:
def gcd(a, b):
....if a == 0 or b == 0:
........print(a + b)
....else:
........if a < b:
............(a, b) = (b, a)
........a = a % b
........gcd(a, b)
a = int(input())
b = int(input())
gcd(a, b)
Функция gcd вызывает саму себя, пока "a" и "b" не равны нулю.
Сокращение дроби.
Алгоритм Евклида можно использовать для написания программы, которая будет сокращать дроби. Чтобы сократить дробь n/m, нужно найти наибольший делитель для чисел n и m. Это делается в функции gcd.
def gcd(a, b):
....global s
....if a == 0 or b == 0:
........s = a + b
....else:
........if a < b:
............(a, b) = (b, a)
........a = a % b
........gcd(a, b)
def ReduceFraction(n, m):
....global s
....gcd(n, m)
....return int(n / s), int(m / s)
n = int(input())
m = int(input())
s = 1
print(*ReduceFraction(n, m))
Вывод.
Очевидно, что умелое использование рекурсии делает текст программы более читабельным. А так же понимание того, что в данной задаче можно использовать рекурсию обычно облегчает как понимание задачи, так и ее программную реализацию.
