Βασική διαφορά – Αναδρομή έναντι Επανάληψης
Η αναδρομή και η επανάληψη μπορούν να χρησιμοποιηθούν για την επίλυση προβλημάτων προγραμματισμού. Η προσέγγιση για την επίλυση του προβλήματος με χρήση αναδρομής ή επανάληψης εξαρτάται από τον τρόπο επίλυσης του προβλήματος. Η βασική διαφορά μεταξύ της αναδρομής και της επανάληψης είναι ότι η αναδρομή είναι ένας μηχανισμός για την κλήση μιας συνάρτησης εντός της ίδιας συνάρτησης ενώ η επανάληψη είναι η εκτέλεση ενός συνόλου εντολών επανειλημμένα έως ότου η δεδομένη συνθήκη είναι αληθής. Η αναδρομή και η επανάληψη είναι σημαντικές τεχνικές για την ανάπτυξη αλγορίθμων και τη δημιουργία εφαρμογών λογισμικού.
Τι είναι η αναδρομή;
Όταν μια συνάρτηση καλεί τον εαυτό της εντός της συνάρτησης, είναι γνωστή ως Αναδρομή. Υπάρχουν δύο τύποι αναδρομής. Είναι πεπερασμένη αναδρομή και άπειρη αναδρομή. Η πεπερασμένη αναδρομή έχει μια καταληκτική συνθήκη. Η άπειρη αναδρομή δεν έχει καταληκτική συνθήκη.
Η αναδρομή μπορεί να εξηγηθεί χρησιμοποιώντας το πρόγραμμα για τον υπολογισμό παραγοντικών παραγόντων.
n!=n(n-1)!, εάν n>0
n!=1, εάν n=0;
Ανατρέξτε στον παρακάτω κωδικό για να υπολογίσετε παραγοντικό του 3(3!=321).
intmain () {
int value=factorial (3);
printf("Το παραγοντικό είναι %d\n", τιμή);
return 0;
}
infactorial (intn) {
if(n==0) {
επιστροφή 1;
}
άλλο {
return n παραγοντικό(n-1);
}
}
Όταν καλείτε παραγοντικό (3), αυτή η συνάρτηση θα καλέσει παραγοντικό (2). Όταν καλείτε παραγοντικό (2), αυτή η συνάρτηση θα καλέσει παραγοντικό (1). Τότε το παραγοντικό (1) θα καλέσει παραγοντικό (0). Το παραγοντικό (0) θα επιστρέψει 1. Στο παραπάνω πρόγραμμα, η συνθήκη n==0 στο «αν μπλοκ» είναι η βασική συνθήκη. Σύμφωνα με το Likewise, η παραγοντική συνάρτηση καλείται ξανά και ξανά.
Οι αναδρομικές συναρτήσεις σχετίζονται με τη στοίβα. Στο C, το κύριο πρόγραμμα μπορεί να έχει πολλές λειτουργίες. Άρα, main () είναι η συνάρτηση κλήσης και η συνάρτηση που καλείται από το κύριο πρόγραμμα είναι η συνάρτηση που καλείται. Όταν καλείται η συνάρτηση, ο έλεγχος δίνεται στην καλούμενη συνάρτηση. Αφού ολοκληρωθεί η εκτέλεση της συνάρτησης, το στοιχείο ελέγχου επιστρέφει στο main. Στη συνέχεια το κύριο πρόγραμμα συνεχίζεται. Έτσι, δημιουργεί μια εγγραφή ενεργοποίησης ή ένα πλαίσιο στοίβας για να συνεχίσει την εκτέλεση.
Εικόνα 01: Αναδρομή
Στο παραπάνω πρόγραμμα, όταν καλείτε το παραγοντικό (3) από το κύριο, δημιουργεί μια εγγραφή ενεργοποίησης στη στοίβα κλήσεων. Στη συνέχεια, δημιουργείται παραγοντικό (2) πλαίσιο στοίβας πάνω από τη στοίβα και ούτω καθεξής. Η εγγραφή ενεργοποίησης διατηρεί πληροφορίες για τοπικές μεταβλητές κ.λπ. Κάθε φορά που καλείται η συνάρτηση, δημιουργείται ένα νέο σύνολο τοπικών μεταβλητών στο επάνω μέρος της στοίβας. Αυτά τα πλαίσια στοίβας μπορούν να επιβραδύνουν την ταχύτητα. Ομοίως στην αναδρομή, μια συνάρτηση καλεί τον εαυτό της. Η χρονική πολυπλοκότητα για μια αναδρομική συνάρτηση βρίσκεται από τον αριθμό των φορών που καλείται η συνάρτηση. Η χρονική πολυπλοκότητα για μία κλήση συνάρτησης είναι O(1). Για n αριθμό επαναλαμβανόμενων κλήσεων, η χρονική πολυπλοκότητα είναι O(n).
Τι είναι Επανάληψη;
Η επανάληψη είναι ένα μπλοκ εντολών που επαναλαμβάνεται ξανά και ξανά έως ότου η δεδομένη συνθήκη είναι αληθής. Η επανάληψη μπορεί να επιτευχθεί χρησιμοποιώντας "for loop", "do-while loop" ή "while loop". Η σύνταξη "for loop" είναι η εξής.
για (αρχικοποίηση, συνθήκη, τροποποίηση) {
// δηλώσεις;
}
Εικόνα 02: "για διάγραμμα ροής βρόχου"
Το βήμα προετοιμασίας εκτελείται πρώτο. Αυτό το βήμα είναι η δήλωση και η προετοιμασία μεταβλητών ελέγχου βρόχου. Εάν η συνθήκη είναι αληθής, εκτελούνται οι εντολές μέσα στα σγουρά άγκιστρα. Αυτές οι εντολές εκτελούνται έως ότου η συνθήκη είναι αληθής. Εάν η συνθήκη είναι ψευδής, το στοιχείο ελέγχου πηγαίνει στην επόμενη δήλωση μετά τον βρόχο "for". Μετά την εκτέλεση των εντολών μέσα στον βρόχο, το στοιχείο ελέγχου πηγαίνει στην ενότητα τροποποίησης. Είναι η ενημέρωση της μεταβλητής ελέγχου βρόχου. Στη συνέχεια, η κατάσταση ελέγχεται ξανά. Εάν η συνθήκη είναι αληθής, οι εντολές μέσα στα σγουρά άγκιστρα θα εκτελεστούν. Με αυτόν τον τρόπο επαναλαμβάνεται ο βρόχος "for".
Στο βρόχο "while", οι εντολές εντός του βρόχου εκτελούνται έως ότου η συνθήκη είναι αληθής.
while (συνθήκη){
//statements
}
Στο βρόχο "do-while", η συνθήκη ελέγχεται στο τέλος του βρόχου. Έτσι, ο βρόχος εκτελείται τουλάχιστον μία φορά.
do{
//statements
} ενώ(συνθήκη)
Το πρόγραμμα για την εύρεση του παραγοντικού του 3 (3!) χρησιμοποιώντας επανάληψη ("for loop") έχει ως εξής.
int main(){
intn=3, παραγοντικό=1;
inti;
for(i=1; i<=n; i++){
factorial=παραγοντικόi;
}
printf("Το παραγοντικό είναι %d\n", παραγοντικό);
return 0;
}
Ποιες είναι οι ομοιότητες μεταξύ της αναδρομής και της επανάληψης;
- Και οι δύο είναι τεχνικές για την επίλυση ενός προβλήματος.
- Η εργασία μπορεί να λυθεί είτε με αναδρομή είτε με επανάληψη.
Ποια είναι η διαφορά μεταξύ της αναδρομής και της επανάληψης;
Αναδρομή εναντίον Επανάληψης |
|
| Η αναδρομή είναι μια μέθοδος κλήσης μιας συνάρτησης εντός της ίδιας συνάρτησης. | Η επανάληψη είναι ένα μπλοκ εντολών που επαναλαμβάνεται μέχρι να είναι αληθής η δεδομένη συνθήκη. |
| Διαστημική πολυπλοκότητα | |
| Η πολυπλοκότητα του χώρου των αναδρομικών προγραμμάτων είναι υψηλότερη από τις επαναλήψεις. | Η πολυπλοκότητα του χώρου είναι μικρότερη σε επαναλήψεις. |
| Ταχύτητα | |
| Η εκτέλεση της αναδρομής είναι αργή. | Κανονικά, η επανάληψη είναι ταχύτερη από την αναδρομή. |
| Κατάσταση | |
| Εάν δεν υπάρχει συνθήκη τερματισμού, μπορεί να υπάρξει άπειρη αναδρομή. | Αν η συνθήκη δεν γίνει ποτέ ψευδής, θα είναι μια άπειρη επανάληψη. |
| Στοίβα | |
| Σε αναδρομή, η στοίβα χρησιμοποιείται για την αποθήκευση τοπικών μεταβλητών όταν καλείται η συνάρτηση. | Σε μια επανάληψη, η στοίβα δεν χρησιμοποιείται. |
| Αναγνωσιμότητα κώδικα | |
| Ένα αναδρομικό πρόγραμμα είναι πιο ευανάγνωστο. | Το επαναληπτικό πρόγραμμα είναι πιο δύσκολο στην ανάγνωση από ένα αναδρομικό πρόγραμμα. |
Σύνοψη – Αναδρομή εναντίον Επανάληψης
Αυτό το άρθρο εξέτασε τη διαφορά μεταξύ αναδρομής και επανάληψης. Και τα δύο μπορούν να χρησιμοποιηθούν για την επίλυση προβλημάτων προγραμματισμού. Η διαφορά μεταξύ της αναδρομής και της επανάληψης είναι ότι η αναδρομή είναι ένας μηχανισμός για την κλήση μιας συνάρτησης μέσα στην ίδια συνάρτηση και η επανάληψη της για την εκτέλεση ενός συνόλου εντολών επανειλημμένα έως ότου η δεδομένη συνθήκη είναι αληθής. Εάν ένα πρόβλημα μπορεί να λυθεί σε αναδρομική μορφή, μπορεί επίσης να λυθεί χρησιμοποιώντας επαναλήψεις.
Λήψη της έκδοσης PDF του Recursion vs Iteration
Μπορείτε να κατεβάσετε την έκδοση PDF αυτού του άρθρου και να τη χρησιμοποιήσετε για σκοπούς εκτός σύνδεσης σύμφωνα με τη σημείωση παραπομπής. Κάντε λήψη της έκδοσης PDF εδώ Διαφορά μεταξύ αναδρομής και επανάληψης
