Πληροφορική Ι — Εβδομάδα 9

Αναδρομή

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

Βασική περίπτωση (τερματίζει) + αναδρομικό βήμα (καλεί τον εαυτό της, για μικρότερο υποπρόβλημα).

Πρώτα, μόνο η βασική περίπτωση — δουλεύει μόνο για n=0:

Προσθέτουμε το αναδρομικό βήμα — τώρα δουλεύει για κάθε n:

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

Χωρίς βασική περίπτωση → RecursionError. Επικαλυπτόμενα υποπροβλήματα → εκθετικός χρόνος.

Δέντρο κλήσεων του fib(5)

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

fib(3) ×2, fib(2) ×3 — οι επικαλύψεις πολλαπλασιάζονται εκθετικά.

Memoization με functools.lru_cache

Ο decorator “θυμάται” αποτελέσματα ήδη υπολογισμένων κλήσεων.

Γεννήτριες: yield

Παράγει τιμές τεμπέλικα (lazily) — μία-μία, κατ’ απαίτηση.

Ταξινόμηση με συγχώνευση

flowchart TD
    A["38 27 43 3 · 9 82 10"] --> B["38 27 43 3"] & C["9 82 10"]
    B --> D["38 27"] & E["43 3"]
    C --> F["9"] & G["82 10"]
    D & E --> BM["3 27 38 43"]
    F & G --> CM["9 10 82"]
    BM & CM --> AM["3 9 10 27 38 43 82"]

Κάτω: χώρισε στη μέση. Πάνω: συγχώνευσε ταξινομημένα.

Merge sort — ο κώδικας

Διαίρει, λύσε αναδρομικά, συγχώνευσε — γραμμή προς γραμμή:

def mergesort(x):
    if len(x) == 1:              # βασική περίπτωση
        return x
    m = len(x) // 2               # διαίρεσε στη μέση
    return merge(mergesort(x[:m]), mergesort(x[m:]))   # λύσε + συγχώνευσε

Τώρα, εκτελέσιμο:

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

Στην Εβδομάδα 8 είχαμε μόνο τύπους για \(2\times2\)/\(3\times3\). Γενικά:

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

Πρώτα, μόνο η βασική περίπτωση — πίνακας \(1\times1\):

Προσθέτουμε το αναδρομικό βήμα — τώρα δουλεύει για κάθε \(n\):

Μία συνάρτηση αντικαθιστά μια άπειρη οικογένεια τύπων — έναν ανά μέγεθος πίνακα.

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

\(T_n = 2T_{n-1}+1 \Rightarrow T_n = 2^n - 1\).

Naive (στοίβα) vs αναδρομική παραγωγή

Η στοίβα κλήσεων της Python αντικαθιστά τη ρητή στοίβα της Εβδομάδας 5.

Σύνοψη

• Βασική περίπτωση, αναδρομικό βήμα
• RecursionError, εκθετική επανάληψη υπολογισμών
• Memoization (lru_cache), γεννήτριες (yield)
• Merge sort, ορίζουσα \(n\times n\) πίνακα (cofactor expansion), Πύργοι του Ανόι
• Naive (στοίβα) vs αναδρομική παραγωγή του ίδιου προβλήματος

⤺ Πλήρεις σημειώσεις  ·  Πρόγραμμα μαθήματος