Αναδρομή |
Αναδρομή λέγεται η προγραμματιστική τεχνική κατά την οποία ένα πρόβλημα επιλύεται με τη βοήθεια μιάς συνάρτησης η οποία μεταξύ των εκτελέσιμων προτάσεών της περιέχει και κλήσεις στον εαυτό της γιά την επίλυση υπο- προβλημάτων του όλου προβλήματος. Είναι μιά τεχνική με μαθηματικό υπόβαθρο και θεωρητική θεμελίωση η οποία με κατάλληλους χειρισμούς μπορεί ουσιαστικά να αντικαταστήσει όλες τις προγραμματιστικές δομές εκτός από την ακολουθία και την απόφαση. 'Ομως έχει το μειονέκτημα της υπερβολικά πυκνής γραφής που κάνει τα προγράμματα δυσανάγνωστα. Επίσης, η υλοποίησή της απαιτεί περισσότερο χώρο στη μνήμη από ότι μιά συνηθισμένη προγραμματιστική λύση. Έτσι έχει καταλήξει να χρησιμοποιείται μόνον όταν οι άλλες τεχνικές δεν προσφέρουν ικανοποιητικό αποτέλεσμα. Το πρόγραμμα του αρχείου RECURSON.C είναι πιθανότατα το απλούστερο πρόγραμμα αναδρομής που μπορεί να γράψει κανείς και γι΄ αυτό δεν έχει και ιδιαίτερο νόημα. Όμως εξυπηρετεί καλά τον σκοπό της επίδειξης της τεχνικής της αναδρομής. Πρίν ξεκινήσουμε την εξήγηση του προγράμματος προσέξτε τη σύνταξη του προτύπου της συνάρτησης count_dn αλλά και τη δήλωση της ίδιας συνάρτησης. Ο τύπος της παραμέτρου δηλώνεται μαζί με την παράμετρο αντί ξεχωρσιτά, όπως είχαμε συνηθίσει μέχρι τώρα. Εάν όμως δεν έχετε μεταφραστή με επιλογή προτύπων ή δεν θέλετε να χρησιμοποιήσετε αυτή την επιλογή, τότε απλά αντικαταστήστε την υπάρχουσα δήλωση με τη κλασσική count_dn(count) int count; Ας προχωρήσουμε στην περιγραφή του προγράμματος. Στο κυρίως πρόγραμμα έχουμε μιά ακέραια μεταβλητή index που πάιρνει την τιμή 8 και χρησιμοποιείται σαν πραγματική παράμετρος στη κλήση της συνάρτησης count_dn. Αυτή είναι όλη η δουλειά του κυρίως προγράμματος. Η συνάρτηση count_dn δεν επιστρέφει κάποια τιμή στο κυρίως πρόγραμμα και δέχεται μιάν ακέραια τιμή η οποία εκχωρείται στη τυπική παράμετρο count. Στη πρώτη εκτελέσιμη πρότασή της η τιμή της count μειώνεται κατά 1. Στη συνέχεια εμφανίζει ένα μήνυμα που περιέχει την τρέχουσα τιμή της count. Αν η τιμή της count είναι μεγαλύτερη του μηδενός τότε η συνάρτηση καλεί τον εαυτό της με πραγματική παράμετρο την τιμή της τυπικής παραμέτρου count. Τελικά εμφανίζεται ακόμη ένα μήνυμα που περιέχει πάλι την τρέχουσα τιμή της count και η συνάτηση τερματίζεται επιστρέφοντας στο κυρίως πρόγραμμα. Το αποτέλεσμα δίνεται παρακάτω. The value of the count is 7 The value of the count is 6 The value of the count is 5 The value of the count is 4 The value of the count is 3 The value of the count is 2 The value of the count is 1 The value of the count is 0 Now the count is 0 Now the count is 1 Now the count is 2 Now the count is 3 Now the count is 4 Now the count is 5 Now the count is 6 Now the count is 7 Τώρα η εξήγηση της αναδρομικής συνάρτησης. Η κλήση μιάς συνάρτησης υλοποιείται από το σύστημα εκτέλεσης (run time system) ως εξής. Στη κύρια μνήμη, και ειδικότερα στην περιοχή της στοίβας (stack), καταλαμβάνεται μιά περιοχή η οποία σχηματικά περιλαμβάνει α) θέσεις μνήμης γιά τις τυπικές παραμέτρους β) θέσεις μνήμης γιά τις τοπικές μεταβλητές γ) τον εκτελέσιμο κώδικα της συνάρτησης δ) την διεύθυνση της εντολής που κάλεσε τη συνάρτηση Αυτή η λογική ισχύει φυσικά και γιά τη περίπτωση που μιά συνάρτηση καλεί τον εαυτό της. Επομένως η πρώτη κλήση της συνάρτησης έχει τα στοιχεία που φαίνονται στο αριστερό πλαίσιο του σχήματος που ακολουθεί. |
![]() |
Αφού εκτελεστούν οι πρώτες προτάσεις της πρώτης κλήσης της συνάρτησης (δηλαδή μείωση count και εκτύπωση count) γίνεται η δεύτερη κλήση. Άρα η δεύτερη κλήση της συνάρτησης γίνεται μέσα από την πρώτη κλήση και πριν αυτή τερματιστεί, δηλαδή η εκτέλεση της πρώτης κλήσης της συνάρτησης διακόπτεται από την δεύτερη κλήση. Η μία πρόταση που απομένει μετά τη κλήση θα εκτελεστεί μετά τον τερματισμό της δεύτερης κλήσης. Η δέυτερη κλήση φαίνεται στο επόμενο πλάισιο του σχήματος. Τι έχει αλλάξει από την πρώτη κλήση; Η τιμή της παραμέτρου count. Τα ίδια ακριβώς ισχύουν και γιά τη δέυτερη κλήση σε σχέση με την τρίτη κλήση της συνάρτησης με μόνη διαφορά πάλι τη μείωση της count κατά μία ακόμη μονάδα. Πότε θα τερματιστούν οι κλήσεις της συνάρτησης; Όταν θα κληθεί μία συνάρτηση με τιμή της πραγματική παραμέτρου ίση με το μηδέν. Τότε η πρόταση κλήσης δεν θα εκτελεστεί, απλά θα εκτελεστούν δύο διαδοχικές εξτυπώσεις της τιμής μηδέν και - επιτέλους - η συγκεκριμένη κλήση της συνάρτησης θα μπορέσει να τερματιστεί αφού δεν εξαρτάται από καμμία άλλη κλήση. Αυτή η διπλή εκτύπωση της τιμής 0 φαίνεται στη λίστα του αποτελέσματος. Πριν από αυτή υπάρχουν οι εκτυπώσεις των τιμών 7, 6 , ..., 1 που οφείλονται στη πρόταση εκτύπωσης που προηγείται στην ακολουθία των εντολών από τη πρόταση της νέας κλήσης της συνάρτησης. Μένουν τώρα οι εκτυπώσεις κατά την αντίστροφη σειρά. Προσέξτε οτι ο τερματισμός της τελευταίας κλήσης της συνάρτησης δεν σημαίνει αυτόματα και τερματισμό όλων των των προηγούμενων κλήσεων. Ας δούμε πάλι το σχήμα. Όταν λήξει η τελευταία κλήση επιστέφει τον έλεγχο στην προ-τελευταία κλήση, σε ποιό όμως σημείο; Στη πρόταση που ακολουθεί αυτή της κλήσης, δηλαδή στη δεύτερη πρόταση εκτ'υπωσης της συνάρτησης. Έτσι με τά το δεύτερο 0 θα τυπωθεί ένα 1 γιατί αυτή είναι η τιμή του count στη προτελευταία κλήση. Μετά από αυτή την εκτύπωση η προτελευταία κλήση θα τερματιστεί και θα επιστρέψει τον έλεγχο στη προ-προτελευταία κλήση κ.ο.κ, μέχρι να φθάσουμε στη πρώτη κλήση και από εκεί στο κυρίως πρόγραμμα. Κάθε βήμα προ ςτα πίσω θα συνοδεύεται από μία ακόμη εκτύπωση. Έτσι έχουμε το τελικό αποτέλεσμα. Γενικά μιά αναδρομική συνάρτηση έχει τη γενική δομή ακολουθία εισόδου (μεταβολή συντελεστή συνθήκης) if (συνθήκη αναδρομής) αναδρομική κλήση (με νέο συντελεστή συνθήκης) ακολουθία εξόδου Η ακολουθία εισόδου εκτελείται πριν την αναδρομική κλήση (forward recursion) και περιλαμβάνει κάποιο είδος μεταβολής στους συντελεστές της συνθήκης αναδρομής. Αλλοιώς θα έχουμε μιά συνεχώς αληθή ή ψευδή συνθήκη που αντιστοιχεί σε μία αναδρομική κλήση που είτε δεν εκτελείται ποτέ ή δεν σταματά ποτέ. Η ακολουθία εξόδου εκτελείται κατά την επιστροφή από την αναδρομική κλήση (backward recursion). Μπορεί μιά από τις ακολουθίες εξόδου ή εισόδου να μην υπάρχουν ή να αποτελούν σύνθετη πρόταση του if. Μπορεί επίσης η μεταβολή του συντελεστή συνθήκης να ενσωματωθεί σε μιά έκφραση που περιλαμβάνεται στη κλήση της αναδρομικής συνάρτησης. Έμμεση ή αμοιβαία αναδρομή έχουμε όταν μία συνάρτηση καλεί κάποια άλλη, αυτή πάλι την πρώτη, κ.ο.κ. |
![]() |
![]() |
![]() |