[Παίζει μουσική] 

DOUG LLOYD: Ίσως πιστεύουν ότι κωδικός χρησιμοποιείται μόνο για να ολοκληρώσει μια εργασία. Μπορείτε να το γράψω. Θα κάνει κάτι. Αυτό είναι λίγο πολύ αυτό. 

Μπορείτε να το υπολογίσουν. Μπορείτε να εκτελέσετε το πρόγραμμα. Είσαι καλό να πάει. 

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

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

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

Έτσι, 5 παραγοντικό είναι 5 φορές 4 φορές 3 φορές 2 φορές 1. Και 4 παραγοντικό είναι 4 φορές 3 φορές 2 φορές 1 και ούτω καθεξής. Μπορείτε να πάρετε την ιδέα. 

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

Τόσο εδώ είναι μερικά facts-- λογοπαίγνιο intended-- σχετικά με το factorial-- παραγοντικό λειτουργία. Το παραγοντικό 1, όπως είπα, είναι 1. Το παραγοντικό 2 είναι 2 φορές 1. Το παραγοντικό του 3 είναι 3 2 φορές φορές 1, και ούτω καθεξής. Μιλήσαμε για 4 και 5 ήδη. 

Αλλά κοιτάζοντας αυτό, δεν είναι αυτή η αλήθεια; Δεν είναι παραγοντικό 2 μόνο 2 φορές το παραγοντικό του 1; Θέλω να πω, το παραγοντικό του 1 είναι 1. Γιατί λοιπόν να μην μπορούμε να πούμε ότι, από το παραγοντικό του 2 είναι 2 φορές 1, είναι πραγματικά ακριβώς 2 φορές το παραγοντικό του 1; 

Και στη συνέχεια επεκτείνει αυτή την ιδέα, Δεν είναι το παραγοντικό του 3 μόλις 3 φορές το παραγοντικό του 2; Και το παραγοντικό του 4 είναι 4 φορές το παραγοντικό του 3, και ούτω καθεξής; Στην πραγματικότητα, η παραγοντικό της οποιοσδήποτε αριθμός μπορεί απλά να εκφραστεί, αν έχουμε το είδος από το υλοποιήσω για πάντα. Είμαστε είδος μπορεί να γενικεύσει το παραγοντικό πρόβλημα όπως είναι η φορές οι παραγοντικό του n μείον 1. Είναι n φορές το προϊόν του όλοι οι αριθμοί κάτω από μένα. 

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

Διαφορετικά, μια συνάρτηση που καλεί itself-- όπως μπορείτε να imagine-- θα μπορούσε να συνεχιστεί για πάντα. Λειτουργία καλεί τη συνάρτηση καλεί τις κλήσεις συναρτήσεων η συνάρτηση καλεί τη συνάρτηση. Εάν δεν έχετε έναν τρόπο να σταματήσει, το πρόγραμμα σας θα κολλήσει αποτελεσματικά σε ένα άπειρο βρόχο. Θα συντριβή τελικά, γιατί αυτό θα ξεμείνει από μνήμη. Αλλά αυτό είναι δίπλα από το σημείο. 

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

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

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

Ποια από αυτά τα βλέμματα όπως και το βασικό σενάριο εδώ; Ποια από τις παρακάτω μοιάζει με το απλούστερη λύση σε ένα πρόβλημα; Έχουμε μια δέσμη των παραγοντικών, και θα μπορούσαμε να συνεχίσουμε πηγαίνει on-- 6, 7, 8, 9, 10, και ούτω καθεξής. 

Αλλά ένα από αυτά μοιάζει με ένα καλή περίπτωση για να είναι η βασική περίπτωση. Είναι μια πολύ απλή λύση. Δεν έχουμε να κάνουμε κάτι το ιδιαίτερο. 

Το παραγοντικό 1 απέχει μόλις 1. Δεν έχουμε να κάνουμε οποιοδήποτε πολλαπλασιασμός καθόλου. Φαίνεται σαν αν θα πάμε να προσπαθήσει να επιλύσει αυτό το πρόβλημα, και πρέπει να σταματήσει η Αναδρομή κάπου, που πιθανόν να θέλετε να σταματήσετε όταν φτάσουμε στο 1. Δεν θέλουμε να σταματήσει πριν από αυτό. 

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

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

Ποια είναι η αναδρομική περίπτωση ίσως μοιάζει; Για κάθε άλλο αριθμό εκτός από 1, ποιο είναι το σχέδιο; Λοιπόν, εάν παίρνετε το παραγοντικό του n, είναι n φορές το παραγοντικό του n μείον 1. 

Εάν παίρνετε το παραγοντικό 3, Είναι 3 φορές το παραγοντικό του 3 μείον 1, ή 2. Και έτσι, αν δεν είμαστε κοιτάζοντας 1, αλλιώς επιστροφή n φορές οι παραγοντικό του n μείον 1. Είναι αρκετά απλό. 

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

Είμαι απλά αφαιρώντας το σγουρό τιράντες, γιατί υπάρχει μόνο μία γραμμή στο εσωτερικό των εν λόγω όρους υποκαταστημάτων. Έτσι, αυτά συμπεριφέρονται με τον ίδιο τρόπο. Αν το n είναι ίσο με 1, επιστροφή 1. Διαφορετικά επιστρέψει n φορές το παραγοντικό του n μείον 1. Έτσι είμαστε καθιστώντας το πρόβλημα μικρότερα. Εάν n ξεκινά ως 5, θα πάμε να επιστρέψετε 5 φορές το παραγοντικό 4. Και θα δούμε σε λίγο, όταν μιλάμε σχετικά με την stack-- κλήση σε ένα άλλο βίντεο όπου μιλάμε για το καλέστε stack-- θα μάθουμε σχετικά με το γιατί ακριβώς αυτή η διαδικασία λειτουργεί. 

Αλλά ενώ παραγοντικό 5 λέει επιστρέψετε 5 φορές παραγοντικό 4, και 4 πρόκειται να πω, εντάξει, καλά, επιστροφή 4 φορές το παραγοντικό του 3. Και όπως μπορείτε να δείτε, είμαστε το είδος της προσέγγισης 1. Είμαστε όλο και πιο πιο κοντά σε αυτή την βασική περίπτωση. 

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

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

Είναι μόνο τέσσερις γραμμές κώδικα. Αυτό είναι αρκετά δροσερό, έτσι δεν είναι; Είναι το είδος του σέξι. 

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

Και οι δύο υπολογίζουν το παραγοντικό του n. Η έκδοση στα αριστερά χρησιμοποιεί αναδρομή για να το κάνουμε. Η έκδοση για το δικαίωμα Χρησιμοποιεί επανάληψη για να το κάνουμε. 

Και ειδοποίηση, θα πρέπει να δηλώσουν μια μεταβλητή ένα προϊόν ακέραιος. Και τότε θα βρόχο. Εφ 'όσον η είναι μεγαλύτερο από μηδέν, εμείς κρατήσει τον πολλαπλασιασμό του εν λόγω προϊόντος από n και Decrementing n μέχρι υπολογίζουμε το προϊόν. Έτσι οι δύο αυτές λειτουργίες, και πάλι, κάνουν ακριβώς το ίδιο πράγμα. Αλλά μην το κάνετε σε τον ίδιο ακριβώς τρόπο. 

Τώρα, είναι δυνατόν να έχουν περισσότερες από μία βάσεις περίπτωση ή περισσότερα από ένα αναδρομική περίπτωση, ανάλογα σε ό, τι η λειτουργία σας προσπαθεί να κάνει. Δεν είναι αναγκαστικά περιορίζεται μόνο στην μία περίπτωση βάσης ή ένα μόνο αναδρομικό περίπτωση. Έτσι, ένα παράδειγμα για κάτι με πολλές περιπτώσεις βάσης θα μπορούσε να είναι η this-- Fibonacci αριθμός ακολουθίας. 

Μπορείτε να ανακαλέσετε από δημοτικό σχολείο ημέρες ότι η ακολουθία Fibonacci ορίζεται όπως this-- το πρώτο στοιχείο είναι 0. Το δεύτερο στοιχείο είναι 1. Και τα δύο αυτά είναι μόνο εξ ορισμού. 

Στη συνέχεια, κάθε άλλο στοιχείο ορίζεται ως το άθροισμα των n 1 και μείον n μείον 2. Έτσι το τρίτο στοιχείο θα είναι 0 και 1 είναι 1. Και στη συνέχεια το τέταρτο στοιχείο θα είναι το δεύτερο στοιχείο, 1, συν το τρίτο στοιχείο, 1. Και αυτό θα είναι 2. Και ούτω καθεξής και ούτω καθεξής. 

Έτσι, σε αυτή την περίπτωση, έχουμε δύο περιπτώσεις βάσης. Αν το n είναι ίσο με 1, 0 επιστρέψει. Αν το n είναι ίσο με 2, 1 επιστρέψει. Διαφορετικά, επιστροφή Fibonacci Ν μείον 1 συν Fibonacci ν μείον 2. 

Έτσι, αυτό είναι πολλαπλές περιπτώσεις βάσης. Τι γίνεται με πολλαπλές αναδρομικές περιπτώσεις; Λοιπόν, υπάρχει κάτι ονομάζεται η εικασία Collatz. Δεν πρόκειται να πω, ξέρετε τι είναι αυτό, γιατί είναι πραγματικά τελικό μας πρόβλημα για το συγκεκριμένο βίντεο. Και αυτό είναι η άσκηση μας να εργαστούν από κοινού. 

Έτσι, εδώ είναι ό, τι η Collatz εικασίες is-- ισχύει για κάθε θετικό ακέραιο. Και αυτό εικάζει ότι είναι πάντα δυνατό να πάρει πίσω με 1 αν ακολουθήσετε τα παρακάτω βήματα. Αν το n είναι 1, να σταματήσει. Έχουμε πίσω στο 1 αν το n είναι 1. 

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

Αλλά έχουμε δύο αναδρομικές περιπτώσεις. Αν το n είναι άρτιο, κάνουμε μία αναδρομική περίπτωση, καλώντας n διαιρείται δια 2. Αν n είναι περιττός, κάνουμε μια διαφορετική αναδρομική περίπτωση στις 3 φορές n + 1. 

Και έτσι ο στόχος για αυτό το βίντεο είναι να λάβει μια δεύτερη, παύση του βίντεο, και να προσπαθήσουμε και να γράψω αυτό αναδρομική συνάρτηση Collatz όπου μπορείτε να περάσετε σε μια τιμή n, και υπολογίζει πόσα βήματα θα χρειάζεται για να φτάσετε στο 1, αν ξεκινήσετε από n και να ακολουθήσετε αυτά τα βήματα μέχρι πάνω. Εάν το η είναι 1, παίρνει 0 βήματα. Διαφορετικά, πρόκειται να πάρτε ένα βήμα συν ωστόσο πολλά βήματα που χρειάζεται για κάθε n διαιρούμενο με 2 αν n είναι ακόμη, ή 3n συν 1 αν ο n είναι περιττός. 

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

Εάν το η είναι 2, παίρνει ένα βήμα για να φτάσετε στο 1. Μπορείτε να ξεκινήσετε με 2. Λοιπόν, 2 δεν είναι ίση με 1. Γι 'αυτό πρόκειται να είναι ένα βήμα συν ωστόσο πολλά βήματα που παίρνει n διαιρείται δια 2. 

2 διαιρείται με 2 είναι 1. Γι 'αυτό παίρνει ένα βήμα συν ωστόσο πολλά βήματα που χρειάζεται για 1. 1 παίρνει μηδέν βήματα. 

Για 3, όπως μπορείτε να δείτε, δεν υπάρχει αρκετά βήματα που εμπλέκονται. Μπορείτε να πάτε από 3. Και τότε θα πάμε να 10, 5, 16, 8, 4, 2, 1. Χρειάζονται επτά βήματα για να πάρετε πίσω στο 1. Και όπως μπορείτε να δείτε, υπάρχει μια ζευγάρι άλλες περιπτώσεις δοκιμής εδώ να δοκιμάσετε το πρόγραμμά σας. Έτσι και πάλι, παύση του βίντεο. Και θα πάω πίσω τώρα έτοιμοι να ποια είναι η πραγματική διαδικασία είναι εδώ, ό, τι αυτό είναι εικασία. 

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

Έτσι, εδώ είναι ένας πιθανός ορισμός της λειτουργίας Collatz. Η βάση μας case-- αν το n είναι ίσο προς 1, θα επιστρέψουμε 0. Δεν λαμβάνει οποιαδήποτε βήματα για να πάρετε πίσω στο 1. 

Σε αντίθετη περίπτωση, έχουμε δύο αναδρομικές cases-- ένα ακόμη αριθμούς και μία για περίεργο. Ο τρόπος που έχω δοκιμάσει ακόμη αριθμούς είναι να ελέγξετε αν ο n mod 2 ισούται με 0. Αυτό είναι βασικά, και πάλι, την ερώτηση, αν θυμηθούμε τι mod is-- αν μου Ν διαίρεσης από 2 δεν υπάρχει υπόλοιπο; Αυτό θα ήταν ένας ακόμη αριθμός. 

Και έτσι, αν n mod 2 ισούται με 0 είναι δοκιμή είναι αυτός ένας άρτιος αριθμός. Αν ναι, θέλω να επιστρέψω 1, επειδή αυτό είναι σίγουρα ένα βήμα συν Collatz της ανεξάρτητα από τον αριθμό είναι το μισό μου. Σε αντίθετη περίπτωση, θέλω να επιστρέψω 1 συν Collatz από 3 φορές n συν 1. Αυτό ήταν το άλλο αναδρομικό βήμα που θα θα μπορούσε να λάβει για τον υπολογισμό της Collatz-- τον αριθμό των βημάτων που χρειάζεται για να πάρει πίσω να δοθεί 1 έναν αριθμό. Έτσι, ελπίζουμε, αυτό το παράδειγμα Σας έδωσα ένα μικρό κομμάτι της μια γεύση των αναδρομικών διαδικασιών. Ας ελπίσουμε ότι, νομίζετε ότι είναι ένας κώδικας λίγο πιο όμορφο, αν εφαρμοστούν σε ένα κομψό, αναδρομικό τρόπο. Αλλά ακόμα και αν δεν είναι, είναι μια αναδρομή πραγματικά ισχυρό εργαλείο παρ 'όλα αυτά. Και γι 'αυτό είναι σίγουρα κάτι για να πάρει το κεφάλι σας γύρω, επειδή θα είστε σε θέση να δημιουργήσουν αρκετά δροσερό προγράμματα χρησιμοποιούν αναδρομή που θα μπορούσαν αλλιώς να είναι πολύπλοκο να γράψω αν χρησιμοποιείτε βρόχους και επανάληψη. Είμαι ο Νταγκ Lloyd. Αυτό είναι CS50.