Recursion, çağrı ağacı ve explicit stack

Recursion üç karar ister: base case, küçülen alt problem ve sonuçları birleştirme. Faktöriyel n!=n·(n−1)! ilişkisiyle yazılır; n=0 için 1 dönmek sınır koşuludur. Negatif girdiyi reddetmezsen küçülme base case'e ulaşmayabilir. Her aktif çağrı çerçevesi alan tüketir; tail recursion'ın otomatik optimize edildiğini Python'da varsayma.

Naif Fibonacci aynı alt problemleri tekrar tekrar çözer: fib(5) hem fib(4) hem fib(3) çağırır, fib(4) tekrar fib(3) hesaplar. Bu çağrı ağacı ile stack derinliği aynı değildir: iş sayısı üstel olabilirken en derin aktif zincir O(n)'dir. Memoization tekrarları kaldırır; iteratif çözüm çağrı stack'ini de kaldırabilir.

Ağaç DFS'sinde recursion okunaklıdır fakat çok uzun zincir stack sınırına ulaşır. Explicit stack, “şimdi işlenecek düğüm” ve gerekirse “geri dönünce yapılacak iş” durumlarını saklar. Preorder, inorder, postorder farkı fonksiyonda düğümü ne zaman işlediğindir. Algoritmanın doğruluğunu sadece recursion kullanmasına bağlama; indüksiyonla alt problem sözleşmesini göster.

def factorial(n):
    if n < 0:
        raise ValueError("negative factorial")
    result = 1
    for x in range(2, n + 1):
        result *= x
    return result
assert factorial(4) == 24