Αναδρομή
Συναρτήσεις που καλούν τον εαυτό τους, και πώς ξέρουν πότε να σταματήσουν.
45 λεπτά
Στο σχολικό βιβλίο: Εισαγωγή στις Αρχές της Επιστήμης των Η/Υ Β΄ Λυκείου, §2.2
Θα μάθεις να
- Να αναγνωρίζεις τη βασική περίπτωση και την αναδρομική κλήση σε μια αναδρομική συνάρτηση.
- Να ακολουθείς τη στοίβα κλήσεων μιας αναδρομικής συνάρτησης βήμα-βήμα.
- Να γράφεις απλές αναδρομικές συναρτήσεις σε Python.
- Να εξηγείς γιατί η απλή αναδρομική Fibonacci είναι αργή και πώς τη διορθώνει η απομνημόνευση.
Μια συνάρτηση που καλεί τον εαυτό της
Αναδρομή (recursion) είναι όταν μια συνάρτηση, για να λύσει ένα πρόβλημα, καλεί τον εαυτό της πάνω σε ένα μικρότερο κομμάτι του ίδιου προβλήματος.
Το παραγοντικό είναι το κλασικό παράδειγμα. Αφού και , ισχύει . Γενικά:
Ο ορισμός μεταφέρεται σχεδόν αυτούσιος σε Python:
Κάθε σωστή αναδρομική συνάρτηση έχει δύο μέρη:
| Μέρος | Ρόλος | Στο παραγοντικό |
|---|---|---|
| Βασική περίπτωση (base case) | απαντά χωρίς αναδρομή, και σταματά την αλυσίδα | n == 0 επιστρέφει 1 |
| Αναδρομική κλήση | λύνει το πρόβλημα με τη βοήθεια ενός μικρότερου | n * factorial(n - 1) |
Η στοίβα κλήσεων
Τι γίνεται στον υπολογιστή όταν τρέχει το factorial(4); Η κλήση δεν μπορεί να τελειώσει πριν πάρει την απάντηση του factorial(3), άρα περιμένει. Ο υπολογιστής κρατά κάθε κλήση που περιμένει, με τις τοπικές της μεταβλητές, σε μια στοίβα κλήσεων (call stack). Η τελευταία κλήση που μπήκε είναι η πρώτη που τελειώνει.
Όταν λείπει η βάση
Αν η βασική περίπτωση λείπει, ή δεν φτάνεται ποτέ, οι κλήσεις δεν σταματούν και η στοίβα μεγαλώνει ώσπου να εξαντληθεί ο χώρος της. Η Python σταματά την αλυσίδα από πριν, σε περίπου επίπεδα, με σφάλμα:
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) που σπάνε το πρόβλημα στα δύο, όπως η δυαδική αναζήτηση και η ταξινόμηση με συγχώνευση.
Οι πύργοι του Ανόι είναι το κλασικό παράδειγμα. Για να μεταφέρεις δίσκους από τον στύλο Α στον Γ, με τον Β βοηθητικό, χωρίς ποτέ μεγάλος δίσκος πάνω σε μικρό: μετάφερε τους πάνω δίσκους στον Β, μετακίνησε τον μεγαλύτερο στον Γ, και ξαναβάλε τους από τον Β πάνω του στον Γ.
Με επανάληψη το ίδιο πρόγραμμα γράφεται πολύ δυσκολότερα.
Όταν η αναδρομή κοστίζει
Η ακολουθία Fibonacci ορίζεται αναδρομικά: , και . Η ευθεία μεταφορά σε κώδικα είναι σωστή αλλά πολύ αργή:
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, αμέσως
Κάθε υπολογίζεται πλέον μία φορά, άρα ο χρόνος γίνεται γραμμικός.
Παραδείγματα
Παράδειγμα 1
Γράψε αναδρομική συνάρτηση που υπολογίζει το άθροισμα των ψηφίων ενός φυσικού αριθμού, και βρες τι επιστρέφει για το .
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Βασική περίπτωση: ένας μονοψήφιος αριθμός έχει άθροισμα ψηφίων τον εαυτό του. Άρα αν
n < 10, επιστρέφουμεn.Αναδρομική κλήση: το τελευταίο ψηφίο είναι
n % 10και ο υπόλοιπος αριθμός είναιn // 10. Άραdigit_sum(n) = n % 10 + digit_sum(n // 10).Σε Python:
def digit_sum(n): if n < 10: return n return n % 10 + digit_sum(n // 10) print(digit_sum(472))Υπολογισμός: το
digit_sum(472)δίνει συνdigit_sum(47), που δίνει συνdigit_sum(4), που είναι η βασική περίπτωση και δίνει . Σύνολο .
Παράδειγμα 2
Πόσες κινήσεις χρειάζονται οι πύργοι του Ανόι για δίσκους; Πόσες για και πόσες για ;
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Αναδρομική σχέση: αν είναι οι κινήσεις για δίσκους, τότε , με .
Πρώτοι όροι: , , , . Κάθε φορά ένα λιγότερο από δύναμη του : .
Για δίσκους: κινήσεις, όσες τυπώνει το πρόγραμμα.
Για δίσκους: κινήσεις. Με μία κίνηση το δευτερόλεπτο, πάνω από δισεκατομμύρια χρόνια. Ο αλγόριθμος είναι σωστός και .
Παράδειγμα 3
Η συνάρτηση total(items) επιστρέφει items[0] + total(items[1:]). Τι λάθος έχει και πώς διορθώνεται;
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Η αναδρομική κλήση είναι σωστή: το πρώτο στοιχείο συν το άθροισμα των υπολοίπων, και η λίστα μικραίνει κατά ένα σε κάθε κλήση.
Λείπει η βασική περίπτωση. Όταν η λίστα αδειάσει, το
items[0]προκαλείIndexError.Διόρθωση: πρόσθεσε στην αρχή
if not items: return 0. Το άθροισμα της κενής λίστας είναι .Και ένα όριο που μένει: για λίστα στοιχείων η συνάρτηση θα ξεπεράσει το όριο της στοίβας. Εκεί η απλή επανάληψη, ή το
sum(items), είναι η σωστή επιλογή.
Πολλαπλή επιλογή
Ασκήσεις
Ποια είναι η βασική περίπτωση της συνάρτησης factorial της ενότητας;
Τα κατάφερες;
- Να αναγνωρίζεις τη βασική περίπτωση και την αναδρομική κλήση σε μια αναδρομική συνάρτηση.
- Να ακολουθείς τη στοίβα κλήσεων μιας αναδρομικής συνάρτησης βήμα-βήμα.
- Να γράφεις απλές αναδρομικές συναρτήσεις σε Python.
- Να εξηγείς γιατί η απλή αναδρομική Fibonacci είναι αργή και πώς τη διορθώνει η απομνημόνευση.
Λύσε τις ασκήσεις πιο πάνω και θα δεις εδώ πού στέκεσαι.