Αναδρομή

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μετάβαση σε: πλοήγηση, αναζήτηση

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

Τυπικός ορισμός της αναδρομής[Επεξεργασία | επεξεργασία κώδικα]

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

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

  • Οι γονείς κάποιου είναι πρόγονοί του (βασική περίπτωση)
  • Οι γονείς των προγόνων κάποιου είναι και πρόγονοί του (αναδρομικό βήμα)

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

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

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

Στο λήμμα αυτό έχει ενσωματωθεί κείμενο από το λήμμα Recursion της Αγγλικής Βικιπαίδειας, η οποία διανέμεται υπό την GNU FDL και την CC-BY-SA 3.0. (ιστορικό/συντάκτες).

Αναδρομικό παραγοντικό[Επεξεργασία | επεξεργασία κώδικα]

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

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

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

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