From Wikipedia, the free encyclopedia
Στα μαθηματικά και την πληροφορική, η αναδρομή είναι μια μέθοδος για τον ορισμό συναρτήσεων κατά την οποία η οριζόμενη συνάρτηση εφαρμόζεται στον ίδιο της τον ορισμό.[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);
}
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.