Rekurencja

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)

# 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)