Πώς λειτουργεί η αναδρομή - εξηγείται με διαγράμματα ροής και βίντεο

"Για να κατανοήσουμε την αναδρομή, πρέπει πρώτα να κατανοήσουμε την αναδρομή."

Η αναδρομή μπορεί να είναι δύσκολη στην κατανόηση - ειδικά για νέους προγραμματιστές. Στην απλούστερη μορφή του, μια αναδρομική συνάρτηση είναι αυτή που αποκαλείται. Επιτρέψτε μου να εξηγήσω με ένα παράδειγμα.

Φανταστείτε ότι θα ανοίξετε την πόρτα του υπνοδωματίου σας και είναι κλειδωμένη. Ο τρίχρονος γιος σου βγαίνει από τη γωνία και σου ενημερώνει ότι έκρυψε το μόνο κλειδί σε ένα κουτί. («Ακριβώς όπως αυτός», νομίζετε.) Είστε αργά για δουλειά και πρέπει πραγματικά να μπείτε στο δωμάτιο για να πάρετε το πουκάμισό σας.

Ανοίγετε το πλαίσιο μόνο για να βρείτε… περισσότερα κουτιά. Κουτιά μέσα από κουτιά. Και δεν ξέρετε ποιο έχει το κλειδί! Πρέπει να αποκτήσετε αυτό το πουκάμισο σύντομα, οπότε πρέπει να σκεφτείτε έναν καλό αλγόριθμο για να βρείτε αυτό το κλειδί.

Υπάρχουν δύο βασικές προσεγγίσεις για τη δημιουργία ενός αλγορίθμου για αυτό το πρόβλημα: επαναληπτικό και αναδρομικό. Ακολουθούν και οι δύο προσεγγίσεις ως διαγράμματα ροής:

Ποια προσέγγιση σας φαίνεται πιο εύκολο;

Η πρώτη προσέγγιση χρησιμοποιεί ένα loop. Ενώ το σωρό δεν είναι άδειο, πιάστε ένα κουτί και κοιτάξτε μέσα από αυτό. Ακολουθεί ένας ψευδοκώδικας εμπνευσμένος από JavaScript που δείχνει τι συμβαίνει. (Ο ψευδοκώδικας γράφεται σαν κώδικας, αλλά προορίζεται να μοιάζει περισσότερο με την ανθρώπινη ομιλία.)

function look_for_key(main_box) { let pile = main_box.make_a_pile_to_look_through(); while (pile is not empty) { box = pile.grab_a_box(); for (item in box) { if (item.is_a_box()) { pile.append(item) } else if (item.is_a_key()) { console.log("found the key!") } } }}

Ο δεύτερος τρόπος χρησιμοποιεί αναδρομή. Θυμηθείτε, η αναδρομή είναι όπου μια συνάρτηση καλείται. Εδώ είναι ο δεύτερος τρόπος στον ψευδοκώδικα.

function look_for_key(box) { for (item in box) { if (item.is_a_box()) { look_for_key(item); } else if (item.is_a_key()) { console.log("found the key!") } } }

Και οι δύο προσεγγίσεις επιτυγχάνουν το ίδιο πράγμα. Ο κύριος σκοπός για τη χρήση της αναδρομικής προσέγγισης είναι ότι μόλις την καταλάβετε, μπορεί να είναι σαφέστερη η ανάγνωση. Στην πραγματικότητα δεν υπάρχει όφελος απόδοσης από τη χρήση αναδρομής. Η επαναληπτική προσέγγιση με βρόχους μπορεί μερικές φορές να είναι ταχύτερη. Ωστόσο, προτιμάται κυρίως η απλότητα της αναδρομής.

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

Βάση βάσης και αναδρομική θήκη

Κάτι που πρέπει να προσέχετε όταν γράφετε μια αναδρομική συνάρτηση είναι ένας άπειρος βρόχος. Αυτό συμβαίνει όταν η λειτουργία συνεχίζει να καλείται… και δεν σταματά ποτέ να καλείται!

Για παράδειγμα, μπορεί να θέλετε να γράψετε μια συνάρτηση αντίστροφης μέτρησης. Θα μπορούσατε να το γράψετε αναδρομικά σε JavaScript ως εξής:

// WARNING: This function contains an infinite loop! function countdown(i) { console.log(i) countdown(i - 1)} countdown(5); // This is the initial call to the function.

Αυτή η λειτουργία θα συνεχίσει να μετράει για πάντα. Εάν εκτελέσετε κατά λάθος κώδικα με άπειρο βρόχο, μπορείτε να πατήσετε "Ctrl-C" για να σκοτώσετε το σενάριό σας. (Ή, αν χρησιμοποιείτε μερικές φορές CodePen σαν εμένα, πρέπει να προσθέσετε το "? Turn_off_js = true" στο τέλος της διεύθυνσης URL.)

Μια αναδρομική συνάρτηση έχει πάντα να πει πότε να σταματήσει να επαναλαμβάνεται. Πρέπει πάντα να υπάρχουν δύο μέρη σε μια αναδρομική συνάρτηση: η αναδρομική θήκη και η βασική θήκη. Η αναδρομική περίπτωση είναι όταν η συνάρτηση καλείται. Η βασική περίπτωση είναι όταν η λειτουργία σταματά να καλείται. Αυτό αποτρέπει άπειρους βρόχους.

Εδώ είναι και πάλι η λειτουργία αντίστροφης μέτρησης, με μια βασική περίπτωση:

function countdown(i) { console.log(i) if (i <= 1) { // base case return; } else { // recursive case countdown(i - 1); } } countdown(5); // This is the initial call to the function.

Μπορεί να μην είναι προφανές ακριβώς τι συμβαίνει σε αυτήν τη λειτουργία. Θα περιγράψω τι συμβαίνει όταν καλείτε τη συνάρτηση αντίστροφης μέτρησης που περνά στο "5".

Ξεκινάμε εκτυπώνοντας τον αριθμό 5 χρησιμοποιώντας console.log. Δεδομένου ότι το πέντε δεν είναι μικρότερο ή ίσο με το μηδέν, πηγαίνουμε στην άλλη δήλωση. Εκεί καλούμε ξανά τη συνάρτηση αντίστροφης μέτρησης με τον αριθμό τέσσερα (5-1 = 4?).

Καταγράφουμε τον αριθμό 4. Και πάλι, δενi είναι λιγότερο ή ίσο με το μηδέν, οπότε πηγαίνουμε στην άλλη δήλωση και αντίστροφη μέτρηση κλήσεων με 3. Αυτό συνεχίζεται μέχριiισούται με μηδέν. Όταν συμβεί αυτό, καταγράφουμε τον αριθμό μηδέν και μετά iείναι μικρότερος ή ίσος με μηδέν. Τελικά φτάνουμε στη δήλωση επιστροφής και βγούμε από τη λειτουργία.

Η στοίβα κλήσης

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

Θα σας δείξω τη στοίβα κλήσεων σε δράση με τη factorialλειτουργία. factorial(5)γράφεται ως 5! και ορίζεται ως εξής: 5! = 5 * 4 * 3 * 2 * 1. Ακολουθεί μια αναδρομική συνάρτηση για τον υπολογισμό του παραγοντικού ενός αριθμού:

function fact(x) { if (x == 1) { return 1; } else { return x * fact(x-1); } }

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

Παρατηρήστε πώς κάθε κλήση factέχει το δικό της αντίγραφο x. Αυτό είναι πολύ σημαντικό για να λειτουργήσει η αναδρομή. Δεν μπορείτε να αποκτήσετε πρόσβαση σε αντίγραφο διαφορετικής λειτουργίας x.

Βρήκατε ακόμα το κλειδί;

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

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

Και χάρη στην αναδρομή, μπορείτε τελικά να βρείτε το κλειδί και να πάρετε το πουκάμισό σας!

Μπορείτε επίσης να παρακολουθήσετε αυτό το βίντεο 5 λεπτών που έκανα σχετικά με την αναδρομή. Θα πρέπει να ενισχύσει αυτές τις έννοιες αναδρομής.

συμπέρασμα

Ελπίζω ότι αυτό το άρθρο σας έδωσε περισσότερη σαφήνεια σχετικά με την αναδρομή στον προγραμματισμό. Αυτό το άρθρο βασίζεται σε ένα μάθημα στο νέο μου βίντεο από το Manning Publications που ονομάζεται Algorithms in Motion. Το μάθημα (και επίσης αυτό το άρθρο) βασίζεται στο εκπληκτικό βιβλίο Αλγόριθμοι Grokking του Adit Bhargava. Είναι αυτός που σχεδίασε όλες τις διασκεδαστικές εικόνες σε αυτό το άρθρο.

Εάν μάθετε καλύτερα μέσω βιβλίων, πάρτε το βιβλίο! Εάν μάθετε καλύτερα μέσω βίντεο, σκεφτείτε να αγοράσετε το μάθημά μου.

Κερδίστε 39% έκπτωση από το μάθημά μου χρησιμοποιώντας τον κωδικό « 39carnes »!

Και τέλος, για να κατανοήσετε πραγματικά την αναδρομή, πρέπει να διαβάσετε ξανά αυτό το άρθρο. ;