Τμήμα Μαθηματικών

Πληροφορική Ι

Εβδομάδα 9 · Αναδρομή

(Οδηγίες χρήσης του διαδραστικού κώδικα: δείτε την αρχική σελίδα.)

1 Αναδρομή

1.1 Η ιδέα της αναδρομής

Η αναδρομή (recursion) βασίζεται στην αρχή «διαίρει και βασίλευε»: διασπάμε ένα πρόβλημα σε υποπροβλήματα ίδιας δομής αλλά απλούστερα, και το καθένα το διασπάμε ξανά — μέχρι να φτάσουμε σε προβλήματα που λύνονται απευθείας.

Μια αναδρομική συνάρτηση είναι απλώς μια συνάρτηση που καλεί τον εαυτό της.

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

τη βασική περίπτωση (base case), που τερματίζει την αναδρομή χωρίς περαιτέρω κλήσεις,
το αναδρομικό βήμα, που καλεί τη συνάρτηση για ένα “μικρότερο” υποπρόβλημα, το οποίο πρέπει να συγκλίνει προς τη βασική περίπτωση.

Κάθε πρόβλημα που λύνεται αναδρομικά μπορεί, καταρχήν, να λυθεί και επαναληπτικά (με βρόχο) — η αναδρομή δεν είναι απαραίτητη, αλλά συχνά είναι πιο φυσική διατύπωση, ειδικά όταν το ίδιο το πρόβλημα ορίζεται μαθηματικά με έναν αναδρομικό τύπο.

Το κλασικό παράδειγμα είναι ο υπολογισμός του παραγοντικού, \(n! = n \times (n-1)!\) με \(0! = 1\):

Ο υπολογισμός του factorial(5) “ανοίγει” μια αλυσίδα κλήσεων προς τα κάτω μέχρι τη βασική περίπτωση, και μετά “κλείνει” προς τα πάνω πολλαπλασιάζοντας:

flowchart TD
    A["factorial(5)"] -->|"5 * …"| B["factorial(4)"]
    B -->|"4 * …"| C["factorial(3)"]
    C -->|"3 * …"| D["factorial(2)"]
    D -->|"2 * …"| E["factorial(1)"]
    E -->|"1 * …"| F["factorial(0) = 1"]
    F -->|"1"| E2["= 1"]
    E2 -->|"1"| D2["= 2"]
    D2 -->|"2"| C2["= 6"]
    C2 -->|"6"| B2["= 24"]
    B2 -->|"24"| A2["= 120"]

Με λίγη «κατασκοπία» βλέπουμε το βάθος της αναδρομής (η εσοχή δείχνει πόσες κλήσεις είναι ανοιχτές):

1.2 Ο αλγόριθμος του Ευκλείδη

Ο αλγόριθμος του Ευκλείδη για τον Μέγιστο Κοινό Διαιρέτη δύο ακεραίων στηρίζεται στην παρατήρηση ότι \(\gcd(x, y) = \gcd(y, x \bmod y)\), με βασική περίπτωση \(\gcd(x, 0) = x\):

1.3 Κίνδυνοι της αναδρομής

Αν παραλειφθεί η βασική περίπτωση (ή δεν συγκλίνει ποτέ σε αυτήν), οι αναδρομικές κλήσεις δεν σταματούν ποτέ, και το πρόγραμμα τερματίζει με σφάλμα υπερχείλισης στοίβας (RecursionError: maximum recursion depth exceeded) — κάθε κλήση συνάρτησης καταναλώνει μνήμη μέχρι να επιστρέψει, και η Python επιβάλλει ένα ανώτατο όριο βάθους αναδρομής.

Ένα δεύτερο, πιο ύπουλο πρόβλημα είναι η περιττή επανάληψη υπολογισμών. Ο “αφελής” αναδρομικός ορισμός της ακολουθίας Fibonacci (\(F_n = F_{n-1} + F_{n-2}\)) καλεί την ίδια τη συνάρτηση εκθετικά πολλές φορές για τα ίδια ορίσματα:

Το πρόβλημα φαίνεται αμέσως στο δέντρο κλήσεων του fib(5): το fib(3) υπολογίζεται 2 φορές, το fib(2) 3 φορές, το fib(1) 2 φορές — και όσο μεγαλώνει το n, αυτές οι επικαλύψεις πολλαπλασιάζονται εκθετικά:

flowchart TD
    F5["fib(5)"] --> F4["fib(4)"]
    F5 --> F3a["fib(3)"]
    F4 --> F3b["fib(3)"]
    F4 --> F2a["fib(2)"]
    F3a --> F2b["fib(2)"]
    F3a --> F1a["fib(1)"]
    F3b --> F2c["fib(2)"]
    F3b --> F1b["fib(1)"]

Ας το μετρήσουμε: πόσες φορές καλείται η fib για κάθε n;

Η αντίστοιχη επαναληπτική έκδοση χρειάζεται μόνο \(O(n)\) βήματα αντί για εκθετικά πολλά, γιατί δεν επαναϋπολογίζει τίποτα:

1.4 Χαρακτηριστικό της Python: memoization με `functools.lru_cache`

Το πρόβλημα του αφελούς fib δεν είναι η αναδρομή, αλλά η επανάληψη ίδιων υπολογισμών.

Η memoization το λύνει: «θυμόμαστε» το αποτέλεσμα κάθε κλήσης, και αν η συνάρτηση ξανακληθεί με τα ίδια ορίσματα, επιστρέφουμε αμέσως την αποθηκευμένη τιμή.

Θα μπορούσαμε να το κάνουμε με το χέρι (ένα λεξικό ως καθολική μεταβλητή — θα το δούμε στην Εβδομάδα 13), αλλά η Python προσφέρει έτοιμο εργαλείο: τον διακοσμητή (decorator) @functools.lru_cache, που «τυλίγει» μια συνάρτηση με ακριβώς αυτή τη λογική, χωρίς να αλλάξουμε το σώμα της:

Σε λογαριθμικό άξονα, η διαφορά είναι εκθετική έναντι γραμμικής — μια ευθεία γραμμή προς τα πάνω σημαίνει ότι κάθε +1 στο n πολλαπλασιάζει τη δουλειά (γράφημα με το matplotlib):

Ο συμβολισμός @functools.lru_cache(maxsize=None) ακριβώς πάνω από τον ορισμό της συνάρτησης λέει στην Python: “κάθε φορά που καλείται η fib_cached με ένα συγκεκριμένο n, έλεγξε πρώτα αν το αποτέλεσμα υπάρχει ήδη αποθηκευμένο· αν ναι, επίστρεψέ το αμέσως, χωρίς να ξανατρέξεις τη συνάρτηση.” Η αναδρομική δομή του κώδικα παραμένει ακριβώς η ίδια με την αρχική fib — απλώς η επανάληψη υπολογισμών εξαφανίζεται.

1.5 Χαρακτηριστικό της Python: γεννήτριες (generators) και το `yield`

Η fib_iterative παραπάνω υπολογίζει το \(F_n\) για ένα συγκεκριμένο \(n\). Τι γίνεται όμως αν θέλουμε μια ακολουθία Fibonacci “χωρίς προκαθορισμένο τέλος”, από την οποία να παίρνουμε όσους όρους χρειαζόμαστε κάθε φορά; Μια γεννήτρια (generator) είναι μια συνάρτηση που, αντί για return, χρησιμοποιεί την εντολή yield: κάθε φορά που καλείται, “παγώνει” στο σημείο του yield και επιστρέφει μια τιμή, αλλά θυμάται πού έμεινε — η επόμενη κλήση συνεχίζει ακριβώς από εκεί, αντί να ξεκινήσει από την αρχή:

Παρατηρήστε ότι fib_generator() δεν “τρέχει” όλο τον κώδικα αμέσως (κάτι τέτοιο θα ήταν αδύνατο, αφού ο βρόχος while True δεν τερματίζει ποτέ!) — απλώς δημιουργεί ένα αντικείμενο-γεννήτρια, έτοιμο να παράγει τιμές μία-μία, “τεμπέλικα” (lazily), στο δικό μας ρυθμό, με κάθε κλήση της next(gen). Είναι η ίδια ιδέα με τις γεννήτριες-εκφράσεις που είδαμε στην Εβδομάδα 4, αλλά εδώ γραμμένη ως πλήρης συνάρτηση, με δικιά της εσωτερική κατάσταση (a, b) που διατηρείται ανάμεσα σε διαδοχικές κλήσεις.

1.6 Ταξινόμηση με συγχώνευση (merge sort)

Η αναδρομή είναι ιδιαίτερα σημαντική στην ανάπτυξη αλγορίθμων ταξινόμησης. Η ταξινόμηση με συγχώνευση (merge sort) υποδιαιρεί συνεχώς τη λίστα στη μέση μέχρι να καταλήξει σε λίστες μήκους 1 (που είναι, τετριμμένα, ήδη ταξινομημένες — η βασική περίπτωση), και μετά συγχωνεύει ξανά τα κομμάτια, διατηρώντας κάθε φορά τη σωστή διάταξη.

Κατεβαίνοντας: χωρίζουμε στη μέση. Ανεβαίνοντας: συγχωνεύουμε ταξινομημένα:

flowchart TD
    A["38 27 43 3 9 82 10"] --> B["38 27 43 3"]
    A --> C["9 82 10"]
    B --> D["38 27"]
    B --> E["43 3"]
    C --> F["9"]
    C --> G["82 10"]
    D --> D1["38"] & D2["27"]
    E --> E1["43"] & E2["3"]
    G --> G1["82"] & G2["10"]
    D1 & D2 --> DM["27 38"]
    E1 & E2 --> EM["3 43"]
    DM & EM --> BM["3 27 38 43"]
    G1 & G2 --> GM["10 82"]
    F & GM --> CM["9 10 82"]
    BM & CM --> AM["3 9 10 27 38 43 82"]

1.7 Ορίζουσα \(n \times n\) πίνακα, αναδρομικά

Στην Εβδομάδα 8 υπολογίσαμε την ορίζουσα μόνο για πίνακες \(2\times2\) και \(3\times3\), με απευθείας τύπους, και αναφέραμε ότι για μεγαλύτερους πίνακες ο τύπος γενικεύεται αναδρομικά, με ανάπτυξη κατά γραμμή (cofactor expansion). Τώρα που ξέρουμε αναδρομή, ας το δούμε: η ορίζουσα ενός \(n\times n\) πίνακα \(A\) γράφεται συναρτήσει οριζουσών \((n-1)\times(n-1)\) πινάκων — των ελασσόνων (minors) που προκύπτουν διαγράφοντας μια γραμμή και μια στήλη:

\[ \det(A) = \sum_{j=0}^{n-1} (-1)^{j} \, A_{0j} \, \det\big(M_{0j}\big), \]

όπου \(M_{0j}\) είναι ο πίνακας που προκύπτει από τον \(A\) διαγράφοντας τη γραμμή \(0\) και τη στήλη \(j\). Η βασική περίπτωση είναι ο πίνακας \(1\times1\), όπου η ορίζουσα είναι απλώς το μοναδικό στοιχείο:

Επαληθεύστε ότι η det συμφωνεί με τις det2/det3 της Εβδομάδας 8 για πίνακες \(2\times2\)/\(3\times3\) — αλλά, σε αντίθεση με εκείνες, η det δουλεύει για οποιοδήποτε μέγεθος πίνακα, χωρίς να χρειάζεται να γράψουμε ξεχωριστό τύπο για κάθε \(n\). Αυτό είναι το χαρακτηριστικό πλεονέκτημα της αναδρομής: μια σύντομη συνάρτηση αντικαθιστά μια άπειρη οικογένεια τύπων, έναν για κάθε \(n\).

Σημείωση

Η ανάπτυξη κατά γραμμή είναι κομψή αλλά αργή: κάνει περίπου \(n!\) πολλαπλασιασμούς συνολικά, οπότε για \(n \gtrsim 10\) γίνεται ήδη πρακτικά μη υπολογίσιμη. Στην πράξη, η ορίζουσα υπολογίζεται πολύ πιο αποδοτικά μέσω της απαλοιφής Gauss (Εβδομάδα 8): το γινόμενο των στοιχείων της διαγωνίου του άνω τριγωνικού πίνακα δίνει την ορίζουσα (με πρόσημο ανάλογα με το πλήθος εναλλαγών γραμμών), σε μόλις \(O(n^3)\) βήματα.

1.8 Οι Πύργοι του Ανόι

Στο γρίφος των Πύργων του Ανόι, \(n\) δίσκοι διαφορετικού μεγέθους είναι στοιβαγμένοι σε έναν στύλο A, σε φθίνουσα σειρά μεγέθους, και θέλουμε να τους μεταφέρουμε όλους σε έναν στύλο προορισμού B, χρησιμοποιώντας έναν βοηθητικό στύλο C, με τους κανόνες: μετακινείται ένας δίσκος τη φορά, μόνο ο πάνω δίσκος μιας στοίβας, και ποτέ μεγαλύτερος δίσκος πάνω σε μικρότερο.

Η αναδρομική λύση είναι κομψή: για να μετακινήσουμε \(n\) δίσκους από το start στο finish (με βοηθητικό το temp),

μετακίνησε τους πάνω \(n-1\) δίσκους από το start στο temp (χρησιμοποιώντας το finish ως βοηθητικό)·
μετακίνησε τον τελευταίο (μεγαλύτερο) δίσκο από το start στο finish·
μετακίνησε τους \(n-1\) δίσκους από το temp στο finish (χρησιμοποιώντας το start ως βοηθητικό).

Αν \(T_n\) είναι το πλήθος των κινήσεων για \(n\) δίσκους, το αναδρομικό βήμα του αλγορίθμου δίνει άμεσα την αναδρομική σχέση

\[ T_n = 2T_{n-1} + 1, \qquad T_1 = 1, \]

αφού λύνουμε δύο φορές το (ίδιο) υποπρόβλημα των \(n-1\) δίσκων, συν μία επιπλέον κίνηση για τον μεγαλύτερο δίσκο. Λύνοντας την αναδρομική σχέση (π.χ. με επαγωγή) προκύπτει ο κλειστός τύπος

\[ T_n = 2^n - 1. \]

Επαληθεύστε ότι ο τύπος \(2^n - 1\) ταιριάζει με το πλήθος κινήσεων που μέτρησε ο αναδρομικός αλγόριθμος παραπάνω. Η εκθετική αύξηση δεν είναι απλώς θεωρητική: σύμφωνα με τον θρύλο, το τέλος του κόσμου θα έρθει όταν μια ομάδα μοναχών ολοκληρώσει τη μετακίνηση \(64\) δίσκων — κάτι που, με έναν δίσκο ανά δευτερόλεπτο, θα απαιτούσε πάνω από \(2^{64}-1 \approx 1{,}8 \times 10^{19}\) δευτερόλεπτα, δηλαδή περισσότερα από 584 δισεκατομμύρια χρόνια.

1.9 Παραγωγή ακέραιων διαμερίσεων, αναδρομικά

Στην Εβδομάδα 5 ορίσαμε την ακέραια διαμέριση (integer partition) ενός φυσικού αριθμού \(n\): έναν τρόπο να γράψουμε τον \(n\) ως άθροισμα θετικών ακεραίων, όπου η σειρά δεν έχει σημασία (π.χ. οι διαμερίσεις του \(4\) είναι \(4\), \(3+1\), \(2+2\), \(2+1+1\), \(1+1+1+1\), άρα \(p(4)=5\)). Τις παράγαμε τότε naively, με μια ρητή στοίβα, αφού δεν ξέραμε ακόμα αναδρομή. Τώρα που ξέρουμε, ας ξαναδούμε το ίδιο πρόβλημα: επιλέγουμε το μεγαλύτερο μέρος (first, με first <= n και όχι μεγαλύτερο από ένα ανώτατο όριο max_part), και αναδρομικά διαμερίζουμε το υπόλοιπο n - first, χρησιμοποιώντας μέρη το πολύ ίσα με first:

Συγκρίνετε με την all_partitions_naive της Εβδομάδας 5: η ρητή στοίβα εκεί κάνει ακριβώς τη δουλειά που κάνει τώρα αυτόματα η Python για εμάς — κάθε αναδρομική κλήση partitions(n - first, first) είναι ένα νέο “εκκρεμές υποπρόβλημα”, και η στοίβα κλήσεων της ίδιας της Python (θυμηθείτε το RecursionError παραπάνω) παίζει τον ρόλο της στοίβας που διαχειριζόμασταν εμείς με το χέρι.

2 Σύνοψη

Σε αυτή την εβδομάδα είδαμε:

Τη δομή κάθε αναδρομικής συνάρτησης: βασική περίπτωση και αναδρομικό βήμα.
Τους κινδύνους της αναδρομής: RecursionError, και η εκθετική επανάληψη υπολογισμών όταν υπάρχουν επικαλυπτόμενα υποπροβλήματα.
Memoization με functools.lru_cache, και γεννήτριες (yield) για οκνηρή παραγωγή ακολουθιών.
Δύο κλασικούς αναδρομικούς αλγορίθμους: ταξινόμηση με συγχώνευση και την αναδρομική επίλυση ενός γρίφου.
Ανάπτυξη κατά γραμμή (cofactor expansion): πώς μια αναδρομική συνάρτηση αντικαθιστά μια άπειρη οικογένεια τύπων (έναν ανά μέγεθος πίνακα) με έναν ενιαίο ορισμό.
Σύγκριση naive (με ρητή στοίβα) και αναδρομικής παραγωγής του ίδιου συνδυαστικού προβλήματος — ό,τι η αναδρομή κάνει αυτόματα, το κάναμε εμείς με το χέρι στην Εβδομάδα 5.

⤺ Πίσω στην αρχική σελίδα / πρόγραμμα μαθήματος · Διαφάνειες αυτής της εβδομάδας