Αναδρομή

Μια συνάρτηση που καλεί τον εαυτό της

Αναδρομή (recursion) είναι όταν μια συνάρτηση, για να λύσει ένα πρόβλημα, καλεί τον εαυτό της πάνω σε ένα μικρότερο κομμάτι του ίδιου προβλήματος.

Το παραγοντικό είναι το κλασικό παράδειγμα. Αφού $5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$ και $4! = 4 \cdot 3 \cdot 2 \cdot 1$, ισχύει $5! = 5 \cdot 4!$. Γενικά:

$$n! = \begin{cases} 1, & n = 0 \\ n \cdot (n-1)!, & n > 0 \end{cases}$$

Ο ορισμός μεταφέρεται σχεδόν αυτούσιος σε Python:

def factorial(n):
    if n == 0:  # βασική περίπτωση
        return 1
    return n * factorial(n - 1)  # αναδρομική κλήση σε μικρότερο πρόβλημα


print(factorial(5))  # 120

Κάθε σωστή αναδρομική συνάρτηση έχει δύο μέρη:

Η στοίβα κλήσεων

Τι γίνεται στον υπολογιστή όταν τρέχει το factorial(4); Η κλήση δεν μπορεί να τελειώσει πριν πάρει την απάντηση του factorial(3), άρα περιμένει. Ο υπολογιστής κρατά κάθε κλήση που περιμένει, με τις τοπικές της μεταβλητές, σε μια στοίβα κλήσεων (call stack). Η τελευταία κλήση που μπήκε είναι η πρώτη που τελειώνει.

Η στοίβα του factorial(4)

Πρώτα η στοίβα γεμίζει, μέχρι τη βασική περίπτωση. Μετά αδειάζει, και σε κάθε βήμα μια κλήση παίρνει την απάντηση που περίμενε.

Βήμα	Βήμα	Κλήση	Τι κάνει	Βάθος στοίβας
Ζωντανή ενημέρωση

Επόμενο βήμαΌλαΕπαναφορά

Όταν λείπει η βάση

Αν η βασική περίπτωση λείπει, ή δεν φτάνεται ποτέ, οι κλήσεις δεν σταματούν και η στοίβα μεγαλώνει ώσπου να εξαντληθεί ο χώρος της. Η Python σταματά την αλυσίδα από πριν, σε περίπου $1000$ επίπεδα, με σφάλμα:

def forever(n):
    return forever(n - 1)  # καμία βασική περίπτωση


try:
    forever(5)
except RecursionError as error:
    print("RecursionError:", error)

Το πρόγραμμα τυπώνει RecursionError: maximum recursion depth exceeded.

Αναδρομή ή επανάληψη;

Κάθε αναδρομή γράφεται και με επανάληψη, και το ανάποδο:

def factorial_loop(n):
    result = 1
    for k in range(2, n + 1):
        result *= k
    return result


print(factorial_loop(5))  # 120

Για το παραγοντικό, η επανάληψη είναι απλούστερη και δεν γεμίζει τη στοίβα. Η αναδρομή κερδίζει όταν το πρόβλημα είναι από τη φύση του αναδρομικό: φάκελοι που περιέχουν φακέλους, δέντρα, ή αλγόριθμοι «διαίρει και βασίλευε» (divide and conquer) που σπάνε το πρόβλημα στα δύο, όπως η δυαδική αναζήτηση και η ταξινόμηση με συγχώνευση.

Οι πύργοι του Ανόι είναι το κλασικό παράδειγμα. Για να μεταφέρεις $n$ δίσκους από τον στύλο Α στον Γ, με τον Β βοηθητικό, χωρίς ποτέ μεγάλος δίσκος πάνω σε μικρό: μετάφερε τους $n - 1$ πάνω δίσκους στον Β, μετακίνησε τον μεγαλύτερο στον Γ, και ξαναβάλε τους $n - 1$ από τον Β πάνω του στον Γ.

def hanoi(n, source, target, spare):
    if n == 0:
        return
    hanoi(n - 1, source, spare, target)
    print("δίσκος", n, "από", source, "σε", target)
    hanoi(n - 1, spare, target, source)


hanoi(3, "Α", "Γ", "Β")  # επτά κινήσεις

Με επανάληψη το ίδιο πρόγραμμα γράφεται πολύ δυσκολότερα.

Όταν η αναδρομή κοστίζει

Η ακολουθία Fibonacci ορίζεται αναδρομικά: $F_0 = 0$, $F_1 = 1$ και $F_n = F_{n-1} + F_{n-2}$. Η ευθεία μεταφορά σε κώδικα είναι σωστή αλλά πολύ αργή:

calls = 0


def fib(n):
    global calls
    calls += 1
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)


for n in [10, 20, 30]:
    calls = 0
    print(n, fib(n), calls)

Ο λόγος: το fib(30) καλεί το fib(29) και το fib(28), αλλά και το fib(29) καλεί ξανά το fib(28). Τα ίδια υποπροβλήματα λύνονται ξανά και ξανά, και οι κλήσεις μεγαλώνουν εκθετικά.

Η διόρθωση λέγεται απομνημόνευση (memoization): κάθε αποτέλεσμα αποθηκεύεται την πρώτη φορά που υπολογίζεται, και απλώς διαβάζεται τις επόμενες.

memo = {}


def fib_memo(n):
    if n < 2:
        return n
    if n not in memo:
        memo[n] = fib_memo(n - 1) + fib_memo(n - 2)
    return memo[n]


print(fib_memo(100))  # 354224848179261915075, αμέσως

Κάθε $F_k$ υπολογίζεται πλέον μία φορά, άρα ο χρόνος γίνεται γραμμικός.

Λυμένα παραδείγματα

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Δείξε τη λύση

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Δείξε τη λύση

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Δείξε τη λύση