Πώς να λύσει Αναδρομή

αναδρομή είναι μια ισχυρή ιδέα στον τομέα της επιστήμης των υπολογιστών , αλλά μπορεί να είναι δύσκολο για τους αρχάριους να κατανοήσουν . Αναδρομή περιλαμβάνει μια λειτουργία ή τη μέθοδο κατ 'επανάληψη επίκληση εαυτό της σε ένα διαφορετικό πλαίσιο , μέχρι να επιτευχθεί μια "βάση " το πλαίσιο και να επιστραφεί. Με άλλα λόγια , να λύσει ένα πρόβλημα , το πρόγραμμα που recontexualizes ως ένα ελαφρώς διαφορετικό πρόβλημα . Κατά την εφαρμογή ενός αναδρομικό αλγόριθμο , πάντα θεωρούν την πιο απλή μορφή του προβλήματος και να καθιερωθεί αυτό το απλουστευμένο παράδειγμα ως « βασικό σενάριο », η οποία θα αναφέρονται όλες οι άλλες εκδοχές του προβλήματος . Οδηγίες
Η 1

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

fib ( int n ) { }

Εδώ , η συνάρτηση υπολογίζει το « νιοστό » Fibonacci αριθμό στην ακολουθία . 2

Καταγράψτε πώς η λειτουργία θα ονομάζεται γενικά . Για παράδειγμα , όταν σας καλούν (fib ) , θα χρησιμοποιήσετε ένα ακέραιο ως το επιχείρημα και να καταγράψει τον ακέραιο που υπολογίζει :

int result = fib ( x ) ?
Εικόνων 3

Ορίστε το « βασικό σενάριο » του προβλήματος αναδρομή σας . Μπορεί να υπάρχουν πολλές περιπτώσεις βάσης . Δεδομένου ότι η ακολουθία Fibonacci απαιτεί δύο αριθμούς , θα χρειαστείτε δύο περιπτώσεις βάση για να εφαρμόσει τη λύση του

if ( n == 0 ) return 0 ? . If ( n == 1 ) επιστροφή 1 ?

4

Ορίστε το αναδρομικό βήμα του προβλήματος αναδρομή σας ως μια μικρότερη , απλούστερη εκδοχή του ίδιου προβλήματος , παραπέμποντας το παράδειγμα επίκληση από το Βήμα 2 . Στο παράδειγμά μας, η ακολουθία Fibonacci είναι μια μαθηματική ακολουθία , όπου κάθε αριθμός στην γραμμή είναι το άθροισμα των δύο προηγούμενων αριθμών στην ακολουθία . Ο αλγόριθμος για να βρει ένα συγκεκριμένο αριθμό Fibonacci πρέπει , επομένως, να επικαλεστεί το ίδιο δύο φορές, μία για τον προηγούμενο αριθμό και μία φορά για τον αριθμό πριν από τον προηγούμενο αριθμό :

int result1 = fib (n - 1 ) ? Int Result2 = fib ( n - 2 ) ?

επιστρέψει result1 + Result2 ?
5

Βάλτε τη λειτουργία από κοινού , π.χ. :

fib ( int n ) {if ( n == 0 ) επιστροφή 0? //base case 1else if ( n == 1 ) επιστροφή 1 ? //base case 2

else { //αναδρομική stepint result1 = fib (n - 1 ) ? int Result2 = fib ( n - 2 ) ?

επιστρέψει result1 + Result2 ? } }

η δομή της « βασική περίπτωση » και « αναδρομικό βήμα " θα είναι το ίδιο για όλες οι αναδρομικές συναρτήσεις , αν και μπορεί να υπάρχουν πολλές περιπτώσεις βάσης και μεγάλη αναδρομική βήματα .
Η
εικόνων