ZAMYLA: Για να κατανοήσουμε αναδρομή, θα πρέπει να πρώτα να κατανοήσουμε αναδρομή. Έχοντας αναδρομή στο πρόγραμμα design μέσα ότι έχετε αυτοαναφορική ορισμούς. Αναδρομικές δομές δεδομένων, για παράδειγμα, είναι δομές δεδομένων που περιλαμβάνουν τον εαυτό τους σε τους ορισμούς τους. Αλλά σήμερα, θα πάμε να επικεντρωθεί σχετικά με αναδρομικές συναρτήσεις. 

Υπενθυμίζουμε ότι οι λειτουργίες λαμβάνουν εισροές, επιχειρήματα, και να επιστρέψει μια τιμή, όπως τους εξόδου που αντιπροσωπεύεται από το διάγραμμα αυτό εδώ. Θα σκεφτούμε το κουτί όπως το σώμα του η συνάρτηση, που περιέχει το σύνολο των οδηγίες που ερμηνεύουν το εισόδου και παρέχουν μία έξοδο. Ρίχνοντας μια πιο προσεκτική ματιά στο εσωτερικό του σώματος της η λειτουργία θα μπορούσε να αποκαλύψει τις κλήσεις προς άλλες λειτουργίες, καθώς και. Πάρτε αυτήν την απλή λειτουργία, foo, ότι παίρνει μια χορδή ως είσοδο και εκτυπώσεις πόσα γράμματα ότι η σειρά έχει. Η strlen λειτουργία, για το μήκος των χορδών, λέγεται, η παραγωγή των οποίων είναι που απαιτούνται για την κλήση στην printf. 

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

Γι 'αυτό πρέπει να βρούμε έναν τρόπο να σπάσει από τις αναδρομικές κλήσεις. Καλούμε αυτό το βασικό σενάριο. Όταν πληρούται η προϋπόθεση βασική περίπτωση, η συνάρτηση επιστρέφει χωρίς να μια άλλη αναδρομική κλήση. Πάρτε αυτή τη λειτουργία, γεια, μια συνάρτηση void που παίρνει έναν int n ως είσοδο. Η βασική περίπτωση έρχεται πρώτη. Εάν n είναι μικρότερη του μηδενός, αντίο εκτύπωσης και Για να επιστρέψει όλες τις άλλες περιπτώσεις, η λειτουργία θα εκτυπώσει ένα γεια και να εκτελέσει η αναδρομική κλήση. Μια άλλη κλήση στην hi συνάρτηση με α μειώνεται τιμή εισόδου. 

Τώρα, ακόμα κι αν εκτυπώσετε γεια, η λειτουργία δεν θα τερματίσει μέχρι να επιστρέψει τύπος επιστροφής της, στην περίπτωση αυτή άκυρη. Έτσι, για κάθε n, εκτός από τη βασική περίπτωση, αυτό το hi συνάρτηση θα επιστρέψει hi κ μείον 1. Δεδομένου ότι αυτή η λειτουργία είναι άκυρη όμως, Δεν θα πληκτρολογήσετε ρητά την επιστροφή εδώ. Θα εκτελέσει μόνο τη λειτουργία. Έτσι, καλώντας hi (3), θα εκτυπώσει και hi εκτελέσει hi (2), η οποία εκτελεί hi (1) μία το οποίο εκτελεί hi (0), όπου η κατάσταση βασική υπόθεση ικανοποιείται. Έτσι hi (0) τυπώνει αντίο και επιστρέφει. 

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

Ας ρίξουμε μια ματιά στο παραγοντικό λειτουργίας που χρησιμοποιείται πιο συχνά σε Υπολογισμοί πιθανοτήτων. Παραγοντικό n είναι το προϊόν της κάθε θετικός ακέραιος μικρότερος και ίση με n. Έτσι παραγοντικό πέντε είναι 5 φορές 4 φορές 3 φορές 2 φορές για να δώσει 1 120. Τέσσερις παραγοντικό είναι 4 φορές 3 φορές 2 φορές για να δώσει 1 24. Και ισχύει ο ίδιος κανόνας για κάθε θετικό ακέραιο. 

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

Για αυτό το παράδειγμα, δείτε πώς 5 παραγοντικό περιλαμβάνει τον πολλαπλασιασμό 4 από 3 με 2 από 1 Και η ίδια αυτή πολλαπλασιασμό βρίσκεται εδώ, η ορισμό του παραγοντικού 4. Έτσι βλέπουμε ότι 5 παραγοντικό είναι μόλις 5 φορές 4 παραγοντικό. Τώρα δεν ισχύει αυτό το μοτίβο 4 παραγοντικό, καθώς; Ναι. Βλέπουμε ότι 4 παραγοντικό περιέχει το πολλαπλασιασμός 3 φορές 2 φορές 1, ο ίδια ορισμός ως 3 παραγοντικό. Έτσι, 4 παραγοντικό είναι ίση με 4 φορές 3 παραγοντικό, και ούτω καθεξής και ούτω καθεξής μας πρότυπο μπαστούνια μέχρι 1 παραγοντικό, η οποία εξ ορισμού είναι ίσο με 1. 

Δεν υπάρχει καμία άλλη θετική ακέραιοι αριστερά. Έτσι, έχουμε το σχέδιο για αναδρομική κλήση μας. n παραγοντικό είναι ίσο με n φορές το παραγοντικό του n μείον 1. Και τη βασική μας υπόθεση; Αυτό θα πρέπει ακριβώς να τον ορισμό μας 1 παραγοντικό. 

Έτσι, τώρα μπορούμε να προχωρήσουμε στο γράψιμο κώδικα για τη συνάρτηση. Για το βασικό σενάριο, θα έχουμε την κατάσταση n ισούται με ίσους 1, όπου θα επιστρέψουμε 1. Στη συνέχεια κινείται πάνω στην αναδρομική κλήση, θα επιστρέψουμε ν φορές την παραγοντικό του n μείον 1. 

Τώρα ας δοκιμάσουν αυτή μας. Ας προσπαθήσουμε παραγοντικό 4. Ανά λειτουργία μας είναι ίση έως 4 φορές παραγοντικού (3). Παραγοντικού (3) είναι ίσο με 3 φορές παραγοντικό (2). Παραγοντικό (2) είναι ίση με 2 φορές παραγοντικού (1), η οποία επιστρέφει 1. Παραγοντικό (2) επιστρέφει τώρα 2 φορές 1, 2. Παραγοντικού (3) μπορεί τώρα να επιστρέψει 3 φορές 2, 6. Και τέλος, παραγοντικό (4) επιστρέφει 4 φορές 6, 24. 

Εάν αντιμετωπίζετε οποιαδήποτε δυσκολία με την αναδρομική κλήση, να υποκρινόμαστε ότι η λειτουργία λειτουργεί ήδη. Τι εννοώ με αυτό είναι ότι θα πρέπει να εμπιστεύονται αναδρομικές κλήσεις σας για να επιστρέψετε οι σωστές αξίες. Για παράδειγμα, αν ξέρω ότι παραγοντικό (5) ισούται με 5 φορές παραγοντικό (4), Πάω να εμπιστεύονται ότι παραγοντικό (4) θα μου δώσει 24. Σκεφτείτε το σαν μια μεταβλητή, αν θα προσφέρει, αν έχετε ήδη οριστεί παραγοντικό (4). Έτσι, για κάθε παραγοντικό (n), είναι το προϊόν των η και το προηγούμενο παραγοντικό. Και αυτό το προηγούμενο παραγοντικό λαμβάνεται με την κλήση παραγοντικό του n μείον 1. 

Τώρα, δείτε αν μπορείτε να εφαρμόσετε ένα αναδρομική λειτουργήσει τον εαυτό σας. Τοποθετήστε το τερματικό σας, ή run.cs50.net, και να γράψει ένα ποσό λειτουργία που παίρνει έναν ακέραιο n και επιστρέφει το άθροισμα όλων των διαδοχικών θετικών ακέραιοι από 1 έως n. Έχω γράψει τα ποσά μερικών τιμές για να σας βοηθήσει μας. Πρώτον, να καταλάβω το κατάσταση βασική υπόθεση. Στη συνέχεια, κοιτάξτε ποσό (5). Μπορείς να την εκφράσουν με όρους άλλο ποσό; Τώρα, τι γίνεται με άθροισμα (4); Πώς μπορείτε να εκφράζουν άθροισμα (4) από την άποψη της άλλης ποσό; 

Μόλις έχετε άθροισμα (5) και το άθροισμα (4) εκφράζονται σε άλλα ποσά, βλέπε αν μπορείτε να αναγνωρίσετε ένα πρότυπο για άθροισμα (n). Αν όχι, δοκιμάστε μερικά άλλα νούμερα και να εκφράσουν τα ποσά τους σε όρους άλλο αριθμό. Με τον προσδιορισμό πρότυπα για διακριτά αριθμοί, είστε καλά στο δρόμο σας για να τον προσδιορισμό του προτύπου για κάθε n. 

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

Ας πούμε ότι θέλετε να εκτελέσετε μια λειτουργία σε κάθε κόμβου σε ένα δυαδικό δένδρο. Πώς θα πάτε γι 'αυτό; Λοιπόν, θα μπορούσατε να γράψετε ένα αναδρομικό λειτουργία που εκτελεί τη λειτουργία στον πατρικό κόμβο και κάνει μια αναδρομική καλέστε την ίδια λειτουργία, περνώντας στην αριστερή δεξιά κόμβους παιδί. Για παράδειγμα, η λειτουργία αυτή, foo, ότι αλλάζει την τιμή του ένα δεδομένο κόμβο και όλα τα παιδιά της σε 1. Η βασική περίπτωση ενός null αιτίες κόμβο η λειτουργία για να επιστρέψει, δείχνοντας ότι δεν υπάρχουν κόμβοι αριστερά σε αυτή την υπο-δέντρο. 

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

Όπως μπορείτε να δείτε, δεν είστε περιορισμένοι σε ένα μόνο αναδρομική κλήση. Ακριβώς όπως πολλοί όπως θα γίνει η δουλειά. Τι εάν είχατε ένα δέντρο όπου κάθε κόμβος είχε τρία παιδιά, Αριστερό, μεσαίο και δεξί; Πώς θα επεξεργαστείτε foo; Λοιπόν, απλά. Απλά προσθέστε μια άλλη αναδρομική κλήση και περάσει στο δείκτη μεσαίας κόμβο. 

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

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

Πάρτε αυτή τη λειτουργία, γεια, μια void συνάρτηση που παίρνει int, n, ως εισροές. Η βασική περίπτωση έρχεται πρώτη. Εάν το η είναι μικρότερο από 0, εκτύπωση "Αντίο" και την επιστροφή.