Να περιγραφεί η λειτουργία της αναδρομής και να σχολιασθεί η χρησιμότητά της.
Σκέψη / Μεθοδολογία: Ερώτηση περιγραφής + σχολιασμός — απαντάται με τον ορισμό της αναδρομής και το σχόλιο για το κόστος/όφελός της από το §3.8.
Λύση:
Ορίζουμε τι είναι αναδρομική συνάρτηση, μετά σχολιάζουμε πλεονεκτήματα (απλότητα/φυσικότητα σύνταξης) και μειονεκτήματα (χρονικό κόστος κλήσεων).
Απάντηση: Μια συνάρτηση ή διαδικασία λέγεται αναδρομική (recursive) όταν καλεί τον εαυτό της, άμεσα ή έμμεσα, με μια απλούστερη περίπτωση του ίδιου προβλήματος — κάθε αναδρομικός αλγόριθμος χρειάζεται μια συνθήκη τερματισμού. Η αναδρομή κάνει συχνά τη λύση πιο κατανοητή και φυσική στη σύνταξη (π.χ. στον υπολογισμό παραγοντικού ή στον αλγόριθμο του Ευκλείδη). Ωστόσο, κάθε κλήση συνάρτησης έχει μη αμελητέο χρονικό κόστος, οπότε η αναδρομή μπορεί να είναι πιο αργή από μια ισοδύναμη επαναληπτική λύση· γι' αυτό, όταν ο χρόνος εκτέλεσης είναι κρίσιμος, προτιμάται η επαναληπτική μέθοδος.
Πρόσεξε:
Να δοθεί αναδρομικός αλγόριθμος υπολογισμού της δύναμης πραγματικού αριθμού υψωμένου σε ακέραια δύναμη.
Σκέψη / Μεθοδολογία: Ο αλγόριθμος δεν δίνεται αυτούσιος στο βιβλίο, αλλά η δύναμη x^n ορίζεται αναδρομικά με το ίδιο ακριβώς πρότυπο του παραγοντικού (§3.8.1): x^0=1, x^n = x · x^(n-1) για n>0. Κατασκευάζουμε τον αλγόριθμο ακολουθώντας πιστά αυτό το πρότυπο.
Λύση:
Γράφουμε πρώτα τον αναδρομικό ορισμό της δύναμης, μετά τον μεταφράζουμε σε αλγόριθμο με τη μορφή του Παραγοντικό από το §3.8.1.
Αλγόριθμος Δύναμη
Δεδομένα // x, n //
Αν n = 0 τότε
power ← 1
αλλιώς
power ← x * Δύναμη(x, n-1)
Τέλος_αν
Αποτελέσματα // power //
Τέλος Δύναμη
Απάντηση: Ορίζουμε: x^n = 1, αν n=0· x^n = x · x^(n-1), αν n>0. Ο παραπάνω αλγόριθμος καλεί τον εαυτό του με ολοένα μικρότερη τιμή του n, μέχρι να φτάσει στη συνθήκη τερματισμού n=0.
Πρόσεξε:
