Рекурсія є дуже важливою концепцією у функціональному програмуванні.
Фундаментальною частиною рекурсії є самопосилання – функції, що викликають самі себе. Він використовується для розв’язування задач, які можна розбити на простіші підзадачі того самого типу.
Класичним прикладом функції, яка реалізується рекурсивно, є функція факторіалу , яка знаходить добуток усіх додатних цілих чисел нижче вказаного числа.
Наприклад, 5! (5 факторіал) дорівнює 5 * 4 * 3 * 2 * 1 (120). Щоб реалізувати це рекурсивно, зауважте, що 5! = 5 * 4!, 4! = 4 * 3!, 3! = 3 * 2! і так далі. Загалом, n! = n * (n-1)!.
Крім того, 1! = 1. Це відоме як базовий випадок , оскільки його можна обчислити без додаткових факторіалів.
Нижче наведено рекурсивну реалізацію функції факториалу.
def factorial(x):
if x == 1:
return 1
else:
return x * factorial(x-1)
print(factorial(5))
приклад використовування 2 функцій для рекурсії
def is_even(x):
if x == 0:
return True
else:
return is_odd(x-1)
def is_odd(x):
return not is_even(x)
print(is_odd(17))
print(is_even(23))
Приклад. Перетворення числа з 10 системи в двійкову
def convert(num):
if num<2:
return num
return (num % 2 + 10 * convert(num // 2))
print(convert(int(input())))
def fib(x):
if x == 0 or x == 1:
return 1
else:
return fib(x-1) + fib(x-2)
print(fib(4))