Μετάβαση στο περιεχόμενο

Αναδρομή

Συναρτήσεις που καλούν τον εαυτό τους, και πώς ξέρουν πότε να σταματήσουν.

45 λεπτά

Στο σχολικό βιβλίο: Εισαγωγή στις Αρχές της Επιστήμης των Η/Υ Β΄ Λυκείου, §2.2

Θα μάθεις να

  1. Να αναγνωρίζεις τη βασική περίπτωση και την αναδρομική κλήση σε μια αναδρομική συνάρτηση.
  2. Να ακολουθείς τη στοίβα κλήσεων μιας αναδρομικής συνάρτησης βήμα-βήμα.
  3. Να γράφεις απλές αναδρομικές συναρτήσεις σε Python.
  4. Να εξηγείς γιατί η απλή αναδρομική Fibonacci είναι αργή και πώς τη διορθώνει η απομνημόνευση.

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

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

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

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

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

Οι κλήσεις του factorial(5)

Οι κλήσεις κατεβαίνουν ως το factorial(0) και μετά οι απαντήσεις ανεβαίνουν. Κάτω από τις μεταβλητές βλέπεις ποιες κλήσεις περιμένουν. Πες τι θα επιστρέψει κάθε κλήση που τελειώνει.

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

Ξεκινάμε. Καμία μεταβλητή δεν έχει ακόμα τιμή.

Μεταβλητές

—

Έξοδος

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

ΜέροςΡόλοςΣτο παραγοντικό
Βασική περίπτωση (base case)απαντά χωρίς αναδρομή, και σταματά την αλυσίδαn == 0 επιστρέφει 1
Αναδρομική κλήσηλύνει το πρόβλημα με τη βοήθεια ενός μικρότερουn * factorial(n - 1)

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

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

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

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

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

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

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

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) που σπάνε το πρόβλημα στα δύο, όπως η δυαδική αναζήτηση και η ταξινόμηση με συγχώνευση.

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

Οι πύργοι του Ανόι με 3 δίσκους

Πάτα Βήμα και κοίτα τη στοίβα: κάθε hanoi περιμένει την πρώτη μικρότερη κλήση, μετακινεί τον δίσκο της και μετά καλεί τη δεύτερη.

  1. def hanoi(n, source, target, spare):
  2. if n == 0:
  3. return
  4. hanoi(n - 1, source, spare, target)
  5. print("δίσκος", n, "από", source, "σε", target)
  6. hanoi(n - 1, spare, target, source)
  7. hanoi(3, "Α", "Γ", "Β") # επτά κινήσεις

Ξεκινάμε. Καμία μεταβλητή δεν έχει ακόμα τιμή.

Μεταβλητές

—

Έξοδος

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

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

Η ακολουθία Fibonacci ορίζεται αναδρομικά: F0=0F_0 = 0, F1=1F_1 = 1 και Fn=Fn−1+Fn−2F_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)
nnFnF_nΚλήσεις
10105555177177
20206765676521 89121\,891
3030832 040832\,0402 692 5372\,692\,537

Ο λόγος: το 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, αμέσως

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

Παραδείγματα

Παράδειγμα 1

Γράψε αναδρομική συνάρτηση που υπολογίζει το άθροισμα των ψηφίων ενός φυσικού αριθμού, και βρες τι επιστρέφει για το 472472.

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

Παράδειγμα 2

Πόσες κινήσεις χρειάζονται οι πύργοι του Ανόι για nn δίσκους; Πόσες για 33 και πόσες για 6464;

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

Παράδειγμα 3

Η συνάρτηση total(items) επιστρέφει items[0] + total(items[1:]). Τι λάθος έχει και πώς διορθώνεται;

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

Πολλαπλή επιλογή

Πολλαπλή επιλογήΆσκηση 1 από 10
Ποια δύο μέρη χρειάζεται κάθε σωστή αναδρομική συνάρτηση;

Ασκήσεις

ΒασικήΆσκηση 1 από 4

Ποια είναι η βασική περίπτωση της συνάρτησης factorial της ενότητας;

Τα κατάφερες;

  • Να αναγνωρίζεις τη βασική περίπτωση και την αναδρομική κλήση σε μια αναδρομική συνάρτηση.
  • Να ακολουθείς τη στοίβα κλήσεων μιας αναδρομικής συνάρτησης βήμα-βήμα.
  • Να γράφεις απλές αναδρομικές συναρτήσεις σε Python.
  • Να εξηγείς γιατί η απλή αναδρομική Fibonacci είναι αργή και πώς τη διορθώνει η απομνημόνευση.

Λύσε τις ασκήσεις πιο πάνω και θα δεις εδώ πού στέκεσαι.

Βρήκες κάποιο λάθος;