Αναδρομή σε

Σχετικά με την έννοια Αναδρομή

Η αναδρομή είναι ένας τρόπος να εκτελείς επανειλημμένα κώδικα μέσα σε μια συνάρτηση, με τη συνάρτηση να καλεί τον εαυτό της. Οι συναρτήσεις που καλούν τον εαυτό τους ονομάζονται αναδρομικές συναρτήσεις. Η αναδρομή μπορεί να ιδωθεί ως ένας ακόμη τρόπος για βρόχους/επαναλήψεις. Και όπως στους βρόχους, μια έκφραση Boolean (λογική τιμή) ή ένας έλεγχος True/False χρησιμοποιείται για να καθοριστεί πότε θα σταματήσει η αναδρομική εκτέλεση.

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

Υλοποίηση με βρόχο έναντι αναδρομικής υλοποίησης

Ο βρόχος και η αναδρομή μπορεί να μοιάζουν μεταξύ τους, καθώς και τα δύο είναι επαναληπτικά. Ωστόσο, διαφέρουν στην όψη, τόσο σε επίπεδο κώδικα όσο και σε επίπεδο υλοποίησης. Ο βρόχος μπορεί να εκτελεστεί μέσα στο ίδιο πλαίσιο στη στοίβα κλήσεων. Αυτό συνήθως γίνεται ενημερώνοντας μία ή περισσότερες τιμές μεταβλητών, ώστε να διατηρείται σταδιακά η κατάσταση για κάθε επανάληψη. Πρόκειται για αποδοτική υλοποίηση, αλλά ο κώδικας μπορεί να φαίνεται κάπως φορτωμένος.

Η αναδρομή, αντί να ενημερώνει την κατάσταση μεταβλητών, μπορεί να περάσει ενημερωμένες τιμές απευθείας ως ορίσματα στην επόμενη κλήση (επανάληψη) της ίδιας συνάρτησης. Έτσι ξεφορτώνεται το σώμα της συνάρτησης και γίνεται πιο ξεκάθαρο το πώς συμβαίνει κάθε ενημέρωση. Ωστόσο, είναι επίσης λιγότερο αποδοτική υλοποίηση, καθώς κάθε κλήση της ίδιας συνάρτησης προσθέτει άλλο ένα πλαίσιο στη στοίβα.

Αναδρομή: γιατί και γιατί όχι;

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

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

Στρατηγική με βρόχο έναντι αναδρομικής στρατηγίας: η ανασφάλεια της Ίντιρα

Η Ίντιρα έχει ρυθμίσει τη μηνιαία σύνταξή της να κατατίθεται αυτόματα στον τραπεζικό της λογαριασμό τη δεύτερη Τετάρτη κάθε μήνα. Η Ίντιρα ανησυχεί μήπως δεν προλαβαίνει να ισοσκελίζει το βιβλιάριο επιταγών της. Φοβάται μήπως γράψει επιταγές πριν κατατεθούν τα χρήματά της. Ζητά από την εγγονή της, την Άντια, να της δώσει μια λίστα με τις ημερομηνίες που θα εμφανιστούν τα χρήματά της στον λογαριασμό της.

Η Άντια, που μόλις μαθαίνει να προγραμματίζει σε Python, γράφει ένα πρόγραμμα βασισμένη στις πρώτες της σκέψεις. Θέλει να επιστρέφει μια list με τις ημερομηνίες κατάθεσης, ώστε να μπορούν να εκτυπωθούν. Θέλει να γράψει μια συνάρτηση που θα δουλεύει για οποιοδήποτε έτος. Σε περίπτωση που αλλάξει το πρόγραμμα (ή σε περίπτωση που άλλοι συγγενείς θέλουν η Άντια να υπολογίζει τα δικά τους προγράμματα καταθέσεων), αποφασίζει ότι η συνάρτηση χρειάζεται μια επιπλέον παράμετρο για την ημέρα της εβδομάδας. Τέλος, η Άντια αποφασίζει ότι η συνάρτηση χρειάζεται μια παράμετρο για το ποια εμφάνιση της ημέρας της εβδομάδας μέσα στον μήνα είναι: η πρώτη, η δεύτερη κ.λπ. Για όλες αυτές τις απαιτήσεις, αποφασίζει να χρησιμοποιήσει την κλάση date που εισάγεται από το datetime. Βάζοντας όλα αυτά μαζί, η Άντια καταλήγει στο εξής:

from datetime import date


def paydates_for_year(year, weekday, ordinal):
    """Returns a list of the matching weekday dates.
    
    Arguments:
        year (int): The year (e.g. 2022).
        weekday (int): The weekday number (e.g. 3 for Wednesday).
        ordinal (int): Which weekday of the month (e.g. 2 for the second day).
    
    Returns:
        output (list): Matching weekday dates.
    """
    
    output = []

    for month in range(1, 13):
        for day_num in range(1, 8):
            if date(year, month, day_num).isoweekday() == weekday:
                output.append(date(year, month, day_num + (ordinal - 1) * 7))
                break
    return output

# find the second Wednesday of the month for all the months in 2022
print(paydates_for_year(2022, 3, 2))

Αυτή η πρώτη εκδοχή δουλεύει, αλλά η Άντια αναρωτιέται αν μπορεί να αναδιοργανώσει τον κώδικα ώστε να χρησιμοποιεί λιγότερες γραμμές και λιγότερους εμφωλευμένους βρόχους. Έχει επίσης διαβάσει ότι είναι καλό να ελαχιστοποιείς τη μεταβολή της κατάστασης, οπότε θα ήθελε να δει αν μπορεί να αποφύγει τη μεταβολή κάποιων μεταβλητών της, όπως οι output, month και day_num.

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

from datetime import date


def paydates_for_year_rec(year, weekday, ordinal, month, day_num, output):
    """Returns a list of the matching weekday dates
    
    Arguments:
        year (int): The year (e.g. 2022).
        weekday (int): The weekday number (e.g. 3 for Wednesday).
        ordinal (int): Which weekday of the month (e.g. 2 for the second day).
        month (int): The month number currently being processed.
        day_num (int): The day number of the month currently being processed.
    
    Returns:
        output (list): Matching weekday dates.
    """
    
    if month == 13:
        return output
        
    if date(year, month, day_num).isoweekday() == weekday:
        return paydates_for_year_rec(
                 year, weekday, ordinal, month + 1, 1, output
                 + [date(year, month, day_num + (ordinal - 1) * 7)]
                 )
    
    return paydates_for_year_rec(year, weekday, ordinal, month, day_num + 1, output)

# find the second Wednesday of the month for all the months in 2022
print(paydates_for_year_rec(2022, 3, 2, 1, 1, []))

Η Άντια είναι χαρούμενη που δεν υπάρχουν πια εμφωλευμένοι βρόχοι, ούτε μεταβαλλόμενη κατάσταση, και που ο κώδικας είναι 2 γραμμές μικρότερος!

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

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

Ακόμη αργότερα, όταν μάθει για τα tuples, η Άντια θα μπορούσε να εξετάσει περαιτέρω τρόπους "βελτιστοποίησης", όπως η χρήση μιας list comprehension με το Calendar.itermonthdates, ή η απομνημόνευση ορισμένων τιμών.

Αναδρομική παραλλαγή: η ουραία κλήση

Ουραία κλήση είναι όταν η τελευταία εντολή μιας συνάρτησης καλεί μόνο τον εαυτό της και τίποτα άλλο. Αυτό το παράδειγμα δεν είναι ουραία κλήση, καθώς η συνάρτηση προσθέτει 1 στο αποτέλεσμα της κλήσης του εαυτού της:

def print_increment(step, max_value):
    if step > max_value:
        return 1
    print(f'The step is {step}')
    return 1 + print_increment(step + 1, max_value)


def main():
    retval = print_increment(1, 2)
    print(f'retval is {retval} after recursion')

if __name__ == "__main__":
    main()

Θα εκτυπώσει:

The step is 1
The step is 2
retval is 3 after recursion

Για να το μετατρέψεις σε ουραία κλήση, κάνε το retval παράμετρο της print_increment.

def print_increment(step, max_value, retval):
    if step > max_value:
        return retval
    print(f'The step is {step}')
    return print_increment(step + 1, max_value, retval + 1)


def main():
    retval = print_increment(1, 2, 1)
    print(f'retval is {retval} after recursion')

if __name__ == "__main__":
    main()

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

Όρια αναδρομής στην Python

Κάποιες γλώσσες μπορούν να βελτιστοποιήσουν τις ουραίες κλήσεις, ώστε κάθε αναδρομική κλήση να επαναχρησιμοποιεί το πλαίσιο στοίβας της πρώτης κλήσης της συνάρτησης (παρόμοια με τον τρόπο που ένας βρόχος επαναχρησιμοποιεί ένα πλαίσιο), αντί να προσθέτει άλλο ένα πλαίσιο στη στοίβα. Η Python δεν είναι μία από αυτές τις γλώσσες. Για να προστατευτεί από την υπερχείλιση της στοίβας, η Python έχει ένα όριο αναδρομής που από προεπιλογή είναι χίλια πλαίσια. Μια εξαίρεση RecursionError πετιέται όταν ο διερμηνευτής ανιχνεύσει ότι το όριο αναδρομής ξεπεράστηκε. Μπορείς να χρησιμοποιήσεις τη μέθοδο sys.setrecursionlimit για να αυξήσεις το όριο αναδρομής, αλλά έτσι ρισκάρεις ένα σφάλμα κατάτμησης κατά την εκτέλεση, που θα καταρρεύσει το πρόγραμμα και ενδεχομένως το λειτουργικό σύστημα.

Πόροι

Για να μάθεις περισσότερα για τη χρήση της αναδρομής στην Python, μπορείς να ξεκινήσεις με

• python-programming: recursion
• Real Python: python-recursion
• Real Python: python-thinking-recursively