Αναδρομή

Ένα σχήμα που περιέχει τον εαυτό του

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

Και τώρα κάνε το ίδιο σε καθένα από τα τρία. Και ξανά, σε καθένα από τα εννιά που προκύπτουν. Αυτό που σχηματίζεται λέγεται τρίγωνο Sierpinski, από τον Πολωνό μαθηματικό Βάτσλαβ Σερπίνσκι, που το περιέγραψε το 1915.

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

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

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

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

def antistrofi(n):
    if n == 0:
        print("Εκκίνηση!")
    else:
        print(n)
        antistrofi(n - 1)

antistrofi(3)

3
2
1
Εκκίνηση!

Η antistrofi(3) τυπώνει το 3 και ζητά από την antistrofi(2) να κάνει τα υπόλοιπα. Αυτή τυπώνει 2 και καλεί την antistrofi(1), που τυπώνει 1 και καλεί την antistrofi(0). Εκεί το n είναι 0: τυπώνεται «Εκκίνηση!» και δεν γίνεται καμία νέα κλήση. Η αλυσίδα σταματά.

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

• τη συνθήκη τερματισμού (base case): την περίπτωση που είναι τόσο απλή ώστε απαντιέται κατευθείαν, χωρίς νέα κλήση. Εδώ, n == 0.
• το αναδρομικό βήμα: κάνει ένα μικρό κομμάτι της δουλειάς και καλεί τον εαυτό της για ένα μικρότερο πρόβλημα. Εδώ, antistrofi(n - 1).

Το παραγοντικό

Το παραγοντικό ενός θετικού ακέραιου $n$ γράφεται $n!$ και είναι το γινόμενο όλων των ακεραίων από το $1$ ως το $n$:

$$5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120$$

Πρόσεξε όμως ότι το $4 \cdot 3 \cdot 2 \cdot 1$ είναι το $4!$. Άρα $5! = 5 \cdot 4!$, και γενικά:

$$n! = n \cdot (n-1)!$$

με αφετηρία το $1! = 1$.

Ο ορισμός είναι ήδη αναδρομικός, και περνά στην Python σχεδόν λέξη προς λέξη:

def paragontiko(n):
    if n == 1:
        return 1
    return n * paragontiko(n - 1)

print(paragontiko(5))

120

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

Οι κλήσεις της paragontiko(4)

Πρώτα οι κλήσεις κατεβαίνουν, μετά οι απαντήσεις ανεβαίνουν. Πριν πατήσεις, πες τι θα επιστρέψει η επόμενη γραμμή.

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

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

Αναδρομή ή βρόχος;

Το παραγοντικό γράφεται και με έναν βρόχο for, όπως έμαθες στους βρόχους:

def paragontiko_vroxos(n):
    apotelesma = 1
    for i in range(1, n + 1):
        apotelesma = apotelesma * i
    return apotelesma

Και οι δύο δίνουν $120$ για το $5$. Ο βρόχος συχνά είναι πιο απλός για έναν υπολογισμό σαν αυτόν. Η αναδρομή γίνεται πολύτιμη όταν το πρόβλημα είναι από τη φύση του «κάτι που περιέχει μικρότερα ίδια»: το τρίγωνο Sierpinski, ένα γενεαλογικό δέντρο, οι φάκελοι μέσα σε φακέλους του υπολογιστή σου.

Ο αριθμός των τριγώνων του Sierpinski, για παράδειγμα, γράφεται αναδρομικά με τον τρόπο που περιγράψαμε το σχήμα:

def trigona(epipedo):
    if epipedo == 0:
        return 1
    return 3 * trigona(epipedo - 1)

print(trigona(4))

81

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

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

Δείξε τη λύση

Η επόμενη συνάρτηση μετρά πόσα ψηφία έχει ένας θετικός ακέραιος:

def psifia(n):
    if n < 10:
        return 1
    return 1 + psifia(n // 10)

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

Δείξε τη λύση