Rekurencja

https://en.wikipedia.org/wiki/Recursion

WPROWADZENIE

Funkcje rekurencyjne to funkcje, które wywołują same siebie bezpośrednio lub za pośrednictwem innych funkcji. Istotne jest zapewnienie, że rekurencja będzie przerwana i nie wystąpi pętla nieskończona.

def print_stars(n):
    """Rekurencyjne wypisywanie n linii z gwiazdką."""
    if n > 0:
        print("*")
        print_stars(n-1)

print_stars(5)                # wywołanie funkcji

# 0! = 1, 1! = 1, n! = n*(n-1)!

def factorial(n):
    """Rekurencyjne obliczanie funkcji silnia n!"""
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorial(n-1)

import math
print(math.factorial(10))   # Python 2.6+
print(factorial(10))

# f(0) = 0, f(1) = 1, f(n) = f(n-1) + f(n-2).

def fibonacci(n):
    """Ciąg Fibonacciego (definicja rekurencyjna)."""
    if n == 0 or n == 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

# avl(0) = 0, avl(1) = 1, avl(h) = avl(h-1) + avl(h-2) + 1,
# minimalna liczba węzłów w drzewie AVL o wysokości h.

def leonardo(h):
    """Liczby Leonardo."""
    if h == 0 or h == 1:
        return h
    else:
        return leonardo(h-1) + leonardo(h-2) + 1

# binomial(n, k) = factorial(n) / (factorial(k) * factorial(n-k)),
# binomial(n, 0) = binomial(n, n) = 1.

def binomial(n, k):
    """Dwumian Newtona w wersji z rekurencyjnej."""
    if k == 0 or k == n:
        return 1
    else:
        return binomial(n-1, k-1) + binomial(n-1, k)