Μενού

Επανάληψη σε C ++

recursion c

Δοκιμάστε Το Όργανο Μας Για Την Εξάλειψη Των Προβλημάτων

Εξερευνήστε όλα σχετικά με την αναδρομή στο C ++ με κλασικά παραδείγματα.

Στο προηγούμενο σεμινάριό μας, μάθαμε περισσότερα σχετικά με τις λειτουργίες στο C ++.

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

Καθώς αναπτύσσουμε πιο περίπλοκες εφαρμογές στο C ++, συναντάμε πολλές απαιτήσεις, ώστε να χρειαστεί να χρησιμοποιήσουμε αρκετές ειδικές έννοιες του C ++. Η αναδρομή είναι μια τέτοια ιδέα.

=> Επισκεφθείτε εδώ για την πλήρη λίστα μαθημάτων C ++.

ΠΡΟΣΤΑΣΙΑ ΣΕ C ++

Σε αυτό το σεμινάριο, θα μάθουμε περισσότερα για την αναδρομή, πού και γιατί χρησιμοποιείται μαζί με μερικά κλασικά παραδείγματα C ++ που εφαρμόζουν την αναδρομή.

Τι θα μάθετε:

Τι είναι η αναδρομή;

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

Η παρακάτω εικόνα απεικονίζει πώς λειτουργεί το Recursion:

Εργασία της αναδρομής

Όπως βλέπουμε στο παραπάνω διάγραμμα, η κύρια συνάρτηση καλεί μια συνάρτηση, funct (). Η λειτουργία Funct () με τη σειρά της καλείται εντός του ορισμού της. Έτσι λειτουργεί η αναδρομή. Αυτή η διαδικασία της συνάρτησης που καλείται θα συνεχιστεί έως ότου παρέχουμε μια συνθήκη τερματισμού που θα την κάνει να τελειώσει.

Συνήθως, παρέχουμε κλάδο κώδικα κατά την εφαρμογή της αναδρομής έτσι ώστε να παρέχουμε μια συνθήκη που θα ενεργοποιήσει την επανάληψη και μια άλλη για την εκτέλεση κανονικής εκτέλεσης.

Βάση αναδρομής

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

Ας δούμε ένα κλασικό παράδειγμα της αναδρομής, της παραγοντικής παράστασης.

Γνωρίζουμε ότι μαθηματικά το παραγοντικό ενός αριθμού n είναι:

ν! = nxn-1x… .x0!
δεδομένου ότι 0! = 1;

Έτσι, το παραγοντικό για το n = 3 θα είναι 3! = 3 × 2!

3! = 3x2x1!
3! = 3x2x2x0!
3! = 3x2x1x1 = 6

Έτσι, μέσω προγραμματισμού μπορούμε να εκφράσουμε αυτόν τον υπολογισμό ως εξής:

int factorial(int n){ if(n <=1) return 1; else return n*factorial(n-1); }

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

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

Δίνεται παρακάτω είναι ένα τέλειο παράδειγμα για τον υπολογισμό του παραγοντικού ενός αριθμού:

#include #include using namespace std; int factorial(int n){ if(n <=1) return 1; else return n*factorial(n-1); } int main() { int num,result; cout<>num; result = factorial(num); cout<

Παραγωγή:

Εισαγάγετε τον αριθμό του οποίου θα υπολογιστεί το παραγοντικό: 10
10! = 3628800

Στο παραπάνω παράδειγμα, εφαρμόζουμε την αναδρομή. Παίρνουμε τον αριθμό του οποίου το παραγοντικό θα βρεθεί από την τυπική είσοδο και μετά θα τον μεταφέρουμε στη συνιστώσα παραγοντικής.

Στη συνάρτηση παραγοντικών, έχουμε δώσει τη βασική συνθήκη ως (n<=1). So, when the base case is reached, the function returns. Using this base case, we can calculate factorial of any number greater than 1.

Κατανομή μνήμης για την αναδρομική κλήση

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

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

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

Υπερχείλιση στοίβας κατά την επανάληψη

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

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

Για παράδειγμα,τροποποιούμε το παραπάνω παραγοντικό πρόγραμμα και αλλάζουμε τη βασική του κατάσταση.

int factorial(int n){ if(n ==1000) return 1; else return n*factorial(n-1); }

Στον παραπάνω κώδικα, έχουμε αλλάξει τη βασική συνθήκη σε (n == 1000). Τώρα, αν δώσουμε τον αριθμό n = 10, μπορούμε να συμπεράνουμε ότι η βασική συνθήκη δεν θα φτάσει ποτέ. Με αυτόν τον τρόπο σε κάποιο σημείο, η μνήμη στη στοίβα θα εξαντληθεί με αποτέλεσμα την υπερχείλιση της στοίβας.

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

Άμεση εναντίον έμμεση επανάληψη

Μέχρι στιγμής σε αναδρομή, έχουμε δει τη λειτουργία να καλείται. Αυτή είναι η άμεση αναδρομή.

Υπάρχει ένας άλλος τύπος αναδρομής, δηλαδή έμμεση επανάληψη. Σε αυτό, μια συνάρτηση καλεί μια άλλη λειτουργία και στη συνέχεια αυτή η λειτουργία καλεί τη λειτουργία κλήσης. Εάν τα f1 και f2 είναι δύο συναρτήσεις. Στη συνέχεια, το f1 καλεί f2 και το f2, με τη σειρά του, καλεί f1. Αυτή είναι μια έμμεση επανάληψη.

πώς να δημιουργήσετε έναν γενικό πίνακα στο java

μεγάλο και εμείς αναθεωρούμε το παραγοντικό μας πρόγραμμα για να δείξουμε άμεση επανάληψη.

#include #include using namespace std; int factorial_b(int); int factorial_a(int n){ if(n <=1) return 1; else return n*factorial_b(n-1); } int factorial_b(int n){ if(n <=1) return 1; else return n*factorial_a(n-1); } int main() { int num, result; cout<>num; result = factorial_a(num); cout<

Παραγωγή:

Εισαγάγετε τον αριθμό του οποίου θα υπολογιστεί το παραγοντικό: 5
5! = 120

Στο παραπάνω παράδειγμα, έχουμε δείξει έμμεση επανάληψη. Η κύρια συνάρτηση καλεί factorial_a. Το Factorial_a καλεί factorial_b. Με τη σειρά factorial_b καλεί factorial_a. Βλέπουμε ότι η έξοδος του προγράμματος δεν επηρεάζεται.

Ουρά και μη ουρά

Μια ουρά αναδρομική συνάρτηση είναι μια αναδρομική συνάρτηση όπου η τελευταία κλήση εκτελείται στη συνάρτηση.

Για παράδειγμα, εξετάστε την ακόλουθη συνάρτηση.

void display(int n){ if(n<=1) return; cout<<” ”<

Στο παραπάνω παράδειγμα, η οθόνη είναι μια ουρά αναδρομικής λειτουργίας έτσι ώστε να είναι η τελευταία κλήση λειτουργίας.

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

Ως αποτέλεσμα, δεν απαιτείται αποθήκευση του τρέχοντος πλαισίου στοίβας για τη λειτουργία.

Πλεονεκτήματα / μειονεκτήματα της αναδρομής σε σχέση με τον επαναληπτικό προγραμματισμό

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

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

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

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

Παραδείγματα αναδρομής

Στη συνέχεια, θα εφαρμόσουμε μερικά από τα παραδείγματα του αναδρομικού προγραμματισμού.

Σειρά Fibonacci

Η σειρά Fibonacci είναι η ακολουθία που δίνεται ως

0 1 1 2 3 5 8 13 ……

Όπως φαίνεται παραπάνω, οι δύο πρώτοι αριθμοί της σειράς Fibonacci είναι 0 και 1. Ο επόμενος αριθμός στη σειρά είναι το άθροισμα των δύο προηγούμενων αριθμών.

Ας εφαρμόσουμε αυτήν τη σειρά χρησιμοποιώντας το Recursion.

#include using namespace std; void fibSeries(int n){ static int n1=0, n2=1, n3; if(n>0){ n3 = n1 + n2; n1 = n2; n2 = n3; cout<num; cout<<'Fibonacci Series for '<

Παραγωγή:

Εισαγάγετε τον αριθμό των στοιχείων για τη σειρά Fibonacci: 10
Fibonacci Series για 10 αριθμούς: 0 1 1 2 3 5 8 13 21 34

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

Palindrome

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

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

Ο αριθμός 291, όταν διαβάζετε από δεξιά προς τα αριστερά, δηλαδή σε αντίστροφη σειρά, έχει την ένδειξη 192. Ως εκ τούτου, το 291 δεν είναι παλίδρο.

#include using namespace std; int reverse_digits(int n, int temp) { if (n == 0) return temp; temp = (temp * 10) + (n % 10); return reverse_digits(n / 10, temp); } int main() { int num; cout<>num; int result = reverse_digits(num, 0); if (result == num) cout << 'Number '<

Παραγωγή:

Εισαγάγετε τον αριθμό για να ελέγξετε το palindrome: 6556
Ο αριθμός 6556 είναι ένα palindrome

Το στιγμιότυπο οθόνης για το ίδιο δίνεται παρακάτω.

Επανάληψη - Palindrome

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

συμπέρασμα

Με αυτό, τελειώσαμε με την επανάληψη. Σε αυτό το σεμινάριο, μελετήσαμε τον αναδρομικό προγραμματισμό, την αναδρομική λειτουργία, τα πλεονεκτήματα / μειονεκτήματά του, καθώς και διάφορα παραδείγματα λεπτομερώς.

Εκτός από αυτά τα παραδείγματα, η αναδρομή χρησιμοποιείται επίσης για την επίλυση ορισμένων τυπικών προβλημάτων, όπως διαβάσεις (inorder / preorder / postorder), πύργοι του Ανόι, BFS traversal, κ.λπ.

=> Επισκεφθείτε εδώ για να μάθετε C ++ από το μηδέν.

Συνιστώμενη ανάγνωση

^