Рекурсивные вызовы в функциях Python
В поиске статей о таком приёме програмирования, как рекурсия, Вы обязательно встретите известную цитату:
“To iterate is human, to recurse divine.” (L. Peter Deutsch)
Итерация свойственна человеку, рекурсия божественна.
Встречаются разные определения рекурсии. Я даю следующее: «Решение задачи через пошаговое упрощение этой задачи до тривиального случая».
Одна из самых простых иллюстраций рекурсивного алгоритма — функция возведения в степень.
def pow_recurse(x,n):
res = 0;
if n == 0:
res = 1 #Число в нулевой степени равно 1
elif n == 1 :
res = x # Число в степени 1 равно самому себе
elif n > 1:
# Рекурисвный вызов. n-1 это упрощение задачи.
res = pow_recurse(x,n-1)*x
return(res)
print(pow_recurse(2,8))
Рекурсия редко бывает самым эффективным, с точки зрения быстродействия, решением. Однако, лаконичность и красота рекурсии для меня бесспорна!
Предлагаю задачу для домашнего решения — написать рекурсивную функцию для поиска чисел Фибоначчи. Решение без использования приёма рекурсии можно увидеть на главной странице сайта python.org
# Python 3: Fibonacci series up to n
def fib(n):
a, b = 0, 1
while a < n:
print(a, end=' ')
a, b = b, a+b
print()
fib(1000)
#0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987
Жду Ваших ответов!