10.7. Αναδρομή

Ένα υποπρόγραμμα καλείται από το κύριο πρόγραμμα ή άλλο υποπρόγραμμα. Υπάρχει όμως και η δυνατότητα ένα υποπρόγραμμα να καλεί τον εαυτό του. Η δυνατότητα αυτή αποκαλείται αναδρομή.

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

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

Αναδρομή ονομάζεται η δυνατότητα ενός υποπρογράμματος να καλεί τον εαυτό του.

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

Ας εξετάσουμε το παράδειγμα υπολογισμού του παραγοντικού:

Το παραγοντικό ορίζεται αναδρομικά ως εξής: [pic]

Τιμή βάσης ή συνθήκη τερματισμού είναι η τιμή που ορίζεται για μία συγκεκριμένη τιμή της παραμέτρου της συνάρτησης, στο παράδειγμα η τιμή είναι 1 για n=0.

Αναδρομική σχέση είναι η n*(n-1)!, όπου η τιμή της συνάρτησης υπολογίζεται με βάση τις προηγούμενες τιμές της συνάρτησης, οι οποίες πρέπει να υπολογιστούν.

Οι συναρτήσεις στη γλώσσα που υλοποιούν τον υπολογισμό του παραγοντικού τόσο αναδρομικά όσο και επαναληπτικά είναι οι εξής.

ΣΥΝΑΡΤΗΣΗ Παραγοντικο(Ν): ΑΚΕΡΑΙΑ ! Υπολογισμός του παραγοντικού με αναδρομική διαδικασία ΜΕΤΑΒΛΗΤΕΣ ΑΚΕΡΑΙΕΣ: Ν ΑΡΧΗ ΑΝ Ν=0 ΤΟΤΕ Παραγοντικό ΑΛΛΙΩΣ Παραγοντικο ΤΕΛΟΣ_ΑΝ ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ ΣΥΝΑΡΤΗΣΗ Παραγοντικό(Ν): ΑΚΕΡΑΙΑ !Υπολογισμός του παραγοντικού με επαναληπτική διαδικασία ΜΕΤΑΒΛΗΤΕΣ ΑΚΕΡΑΙΕΣ: i, Ν ΑΡΧΗ Fact ΓΙΑ i ΑΠΟ 2 ΜΕΧΡΙ Ν Fact ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ

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

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

Ας παρακολουθήσουμε τον τρόπο με τον οποίο υπολογίζεται το 5! με τη χρήση της αναδρομικής συνάρτησης Παραγοντικό().

Εφόσον η παράμετρος της συνάρτησης είναι αρχικά 5, διάφορη δηλαδή του 0, καλείται η συνάρτηση Παραγοντικό(4). Στην συνέχεια επειδή η παράμετρος είναι διάφορη του μηδενός, καλείται το Παραγοντικό(3) και η διαδικασία συνεχίζεται όπως δείχνει το σχήμα μέχρι την κλήση του Παραγοντικό(0).

Παραγοντικό(5) Ν Παραγοντικό 5

Παραγοντικό(4) Ν Παραγοντικό 4

Παραγοντικό(3) Ν Παραγοντικό 3

Παραγοντικό(2) Ν Παραγοντικό 2

Παραγοντικό(1) Ν Παραγοντικό 1

Παραγοντικό(0) Ν Παραγοντικό

Για τη τιμή της παραμέτρου Ν=0 το Παραγοντικό(0) έχει τιμή 1, την τιμή βάσης. Έτσι αρχίζει η αντίστροφη διαδικασία υπολογισμού διαδοχικά του υπολογισμού των συναρτήσεων Παραγοντικό(2)=1*2, Παραγοντικό(3)=2*3, Παραγοντικό(4)=6*4 όπως δείχνει το παρακάτω σχήμα.

Το τελευταίο βήμα είναι ο υπολογισμός του Παραγοντικό(5)=24*5. Η τιμή αυτή δηλαδή 120 είναι η τιμή που η συνάρτηση τελικά επιστρέφει.

Παραγοντικό(5) Ν Παραγοντικό 5 120

Παραγοντικό(4) Ν Παραγοντικό

Παραγοντικό(3) Ν Παραγοντικό 3 6

Παραγοντικό(2) Ν Παραγοντικό 2 2

Παραγοντικό(1) Ν Παραγοντικό

Παραγοντικό(0) Ν Παραγοντικό 0 1

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

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

Προγραμματιστικό περιβάλλον Pascal

FUNCTION factorial(n:INTEGER) : INTEGER; BEGIN IF n=0 THEN factorial:=1 ELSEfactorial:=n*factorial(n-1); END; FUNCTION factorial(n: INTEGER) : INTEGER; VAR i,fact:integer; BEGIN fact:=1; FOR i:=2 TO n DO fact:=i*fact; factorial:=fact END;

Προγραμματιστικό περιβάλλον Βasic FUNCTION Factorial (n) IF n = 0 THEN Factorial = 1 ELSE Factorial = n * Factorial(n - 1) END IF END FUNCTION FUNCTION Factorial (n) fact = 1

FOR i = 2 TO n fact = fact * i NEXT i Factorial = fact END FUNCTION