Αναδρομή, ένα από τα πιο συγκεχυμένα θέματα στον κόσμο του προγραμματισμού. Αφού έχω ένα blog σχετικά με ορισμένες από τις δομές δεδομένων, νομίζω ότι αυτή είναι η κατάλληλη στιγμή για να σας παρουσιάσω σχετικά με την αναδρομή.
Τι είναι η αναδρομή;
Η αναδρομή είναι παρόμοια με έναν βρόχο που κάνει την εργασία ξανά και ξανά όχι κάνοντας βρόχο αλλά καλώντας ξανά τη συνάρτηση μέσα στη συνάρτηση. Ο τρόπος που λειτουργεί είναι ότι δημιουργείτε μια βασική περίπτωση και μετά την αναδρομική περίπτωση. Base case είναι η περίπτωση που κάνει το πρόγραμμά σας να σταματήσει να καλεί τον εαυτό του και θα σας δείξω στον κώδικα.
Έτσι, το πιο διάσημο πρόβλημα που χρησιμοποιεί την αναδρομή για να λύσει είναι ο Fibonacci και ο πύργος του Ανόι.
Για να είμαι σαφής σήμερα, θα επικεντρωθώ κυρίως στην ακολουθία Fibonacci. Μια σύντομη εξήγηση της ακολουθίας Fibonacci είναι ότι το πρώτο ψηφίο της ακολουθίας είναι ένα και το επόμενο είναι το άθροισμα των προηγούμενων και πριν από τα προηγούμενα ψηφία και ούτω καθεξής.
def Fibonacci(n):
if n == 0:
return 0
if n == 1:
return 1
else:
return Fibonacci(n-1)+ Fibonacci(n-2)
print(Fibonacci(5))
Αυτός είναι ο κώδικας της ακολουθίας Fibonacci. Φαίνεται απλό όπως η παραπάνω εξήγηση.
Ας ξεκινήσουμε με την αναδρομική περίπτωση αυτού του προγράμματος που είναι
else: return Fibonacci(n-1)+ Fibonacci(n-2)
Όπως μπορείτε να δείτε, κάλεσα τη συνάρτηση 2 φορές και αυτό που κάνει είναι ότι πηγαίνει ξανά στη συνάρτηση αλλά στέλνοντας τα δεδομένα πίσω μειώνοντας μία και δύο κάθε φορά.
5 είναι τα αρχικά δεδομένα που εισάγουμε στο πρόγραμμα σύμφωνα με τον παραπάνω κώδικα. Καλεί τη συνάρτηση και προχωρά σε όλη τη διαδικασία, περιμένει μέχρι να σταματήσει να καλεί και συνεχίζει τον βαθύτερο κωδικό και στη συνέχεια ολοκληρώνει τον εξωτερικό.
Κάνει την αναδρομή, αλλά δεν έχει αθροίσει ακόμα τη συνάρτηση μπλε και ροζ.
Τώρα ένα από αυτά φτάνει στη βασική περίπτωση (3–2=1). Η θήκη βάσης είναι.
if n == 0:
return 0
if n == 1:
return 1
το πρόγραμμα δεν θα σταματήσει αλλά θα τελειώσει τα υπόλοιπα που έχουν κληθεί.
Επειτα.
Τώρα όλο το αναδρομικό έχει φτάσει στις βασικές του περιπτώσεις. Αυτό που θα κάνει είναι να συνεχίσει την τελευταία λειτουργία.
else: return Fibonacci(n-1)+ Fibonacci(n-2)
Στη συνέχεια προσθέτει αργά όλους τους αριθμούς μέχρι να αθροιστούν όλα τα μπλε και τα ροζ πλαίσια.
Αυτό είναι όλο για το σημερινό ιστολόγιο, ελπίζω να καταλάβετε. αν έχετε οποιαδήποτε ερώτηση, ενημερώστε το στο σχόλιο. ^^
(Αν θέλετε να δείξω πώς να χρησιμοποιώ την αναδρομή στη χελώνα, παρακαλώ ενημερώστε με ότι θα ήθελα πολύ.)
