Μετάβαση στο περιεχόμενο

Αναδρομή

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

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

Στην πληροφορική, πολλοί από τους αλγορίθμους ορίζονται αναδρομικά για προβλήματα όπως της ταξινόμησης (π.χ. η merge sort ή η quick sort), της αναζήτησης σε γράφο και άλλων.

Τυπικός ορισμός της αναδρομής

[Επεξεργασία | επεξεργασία κώδικα]

Στα μαθηματικά και την επιστήμη υπολογιστών, η αναδρομή ορίζει (ή κατασκευάζει) μια τάξη αντικειμένων ή μεθόδων (ή ένα αντικείμενο μιας τάξης), ορίζοντας κάποιες απλές περιπτώσεις ή μεθόδους (συχνά μία και μόνη), και ορίζοντας κανόνες για τη διάσπαση πολύπλοκων περιπτώσεων σε απλούστερες.[2]

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

  • Το τρίγωνο Σιερπίνσκι - μια περιορισμένη αναδρομή τριγώνων που σχηματίζουν ένα φράκταλ
    Οι γονείς κάποιου είναι πρόγονοί του (βασική περίπτωση)
  • Οι γονείς των προγόνων κάποιου είναι και πρόγονοί του (αναδρομικό βήμα)

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

Παρόμοιοι ορισμοί απαντώνται συχνά στα μαθηματικά. Για παράδειγμα, ο τυπικός ορισμός των φυσικών αριθμών στη θεωρία συνόλων είναι: το 1 είναι φυσικός αριθμός και κάθε φυσικός αριθμός έχει έναν επόμενο, που είναι επίσης φυσικός αριθμός.

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

Υπολογισμός παραγοντικού

[Επεξεργασία | επεξεργασία κώδικα]

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

Εναλλακτικά (αλλά ισοδύναμα), το παραγοντικό μπορεί να οριστεί αναδρομικά ως εξής:

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

int paragontiko(int n){
   if (n == 0) return 1;
   else return n * paragontiko(n-1);
}

Αριθμητική και Γεωμετρική Πρόοδος

[Επεξεργασία | επεξεργασία κώδικα]

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

Αντίστοιχα κάθε Γεωμετρική πρόοδος, δηλαδή

Αριθμοί Φιμπονάτσι

[Επεξεργασία | επεξεργασία κώδικα]

Οι αριθμοί της ακολουθίας Φιμπονάτσι ορίζονται αναδρομικά για κάθε φυσικό αριθμό ως εξής:

Για παράδειγμα,

  • Ο τρίτος αριθμός Φιμπονάτσι δίνεται από .
  • Ο τέταρτος αριθμός Φιμπονάτσι δίνεται από .
  • Ο πέμπτος αριθμός Φιμπονάτσι δίνεται από .

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

int fibonacci(int n){
   if (n == 0) return 0;
   else if (n == 1) return 1;
   else return fibonacci(n - 1) + fibonacci(n - 2);
}
  1. Causey, Robert L. (2006). Logic, sets, and recursion (2nd έκδοση). Sudbury, Mass.: Jones and Bartlett Publishers. ISBN 0-7637-3784-4. OCLC 62093042. 
  2. Nerode, Anil· Shore, Richard A. (1985). Recursion Theory. American Mathematical Soc. ISBN 978-0-8218-1447-5.