Рекурсивные вызовы в функциях 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

Жду Ваших ответов!