Αναδρομή

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

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

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

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

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

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

• 

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

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

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

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

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

Παραδείγματα

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

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

$n!=1\cdot 2\cdot \ldots \cdot n.$

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

$n!={\begin{cases}1&{\text{αν }}n=0,\\n\cdot (n-1)!&{\text{αν }}n\geq 1.\end{cases}}$

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

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

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

Κάθε αριθμητική πρόοδος, δηλαδή κάθε ακολουθία πραγματικών αριθμών $a_{1},a_{2},a_{3},\ldots$, όπου $a_{n}=x+(n-1)\cdot d$ για κάποια $x,d\in \mathbb {R}$, μπορεί να οριστεί και αναδρομικά ως

$a_{n}={\begin{cases}x&{\text{αν }}n=1,\\a_{n-1}+d&{\text{αν }}n>1.\end{cases}}$

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

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

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

$F_{n}={\begin{cases}0&{\text{αν }}n=0,\\1&{\text{αν }}n=1,\\F_{n-1}+F_{n-2}&{\text{αν }}n\geq 2.\end{cases}}$

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

• Ο τρίτος αριθμός Φιμπονάτσι δίνεται από $F_{2}=F_{1}+F_{0}=1+0=1$.
• Ο τέταρτος αριθμός Φιμπονάτσι δίνεται από $F_{3}=F_{2}+F_{1}=1+1=2$.
• Ο πέμπτος αριθμός Φιμπονάτσι δίνεται από $F_{4}=F_{3}+F_{2}=2+1=3$.

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

int fibonacci(int n){
   if (n == 0) return 0;
   else if (n == 1) return 1;
   else return fibonacci(n - 1) + fibonacci(n - 2);
}

Δείτε επίσης

• Μαθηματική επαγωγή
• Δυναμικός προγραμματισμός
• Διαίρει και βασίλευε (υπολογιστές)

Βιβλιογραφία

• Dijkstra, Edsger W. (1960). «Recursive Programming». Numerische Mathematik 2 (1): 312–318. doi:10.1007/BF01386232. 
• Johnsonbaugh, Richard (2004). Discrete Mathematics. Prentice Hall. ISBN 978-0-13-117686-7. 
• Hofstadter, Douglas (1999). Gödel, Escher, Bach: an Eternal Golden Braid. Basic Books. ISBN 978-0-465-02656-2. 
• Shoenfield, Joseph R. (2000). Recursion Theory. A K Peters Ltd. ISBN 978-1-56881-149-9. 
• Causey, Robert L. (2001). Logic, Sets, and Recursion. Jones & Bartlett. ISBN 978-0-7637-1695-0. 
• Cori, Rene· Lascar, Daniel· Pelletier, Donald H. (2001). Recursion Theory, Gödel's Theorems, Set Theory, Model Theory. Oxford University Press. ISBN 978-0-19-850050-6. 
• Barwise, Jon· Moss, Lawrence S. (1996). Vicious Circles. Stanford Univ Center for the Study of Language and Information. ISBN 978-0-19-850050-6.  - offers a treatment of corecursion.
• Rosen, Kenneth H. (2002). Discrete Mathematics and Its Applications. McGraw-Hill College. ISBN 978-0-07-293033-7. 
• Cormen, Thomas H.· Leiserson, Charles E.· Rivest, Ronald L.· Stein, Clifford (2001). Introduction to Algorithms. Mit Pr. ISBN 978-0-262-03293-3. 
• Kernighan, B.· Ritchie, D. (1988). The C programming Language. Prentice Hall. ISBN 978-0-13-110362-7. 
• Stokey, Nancy· Robert Lucas· Edward Prescott (1989). Recursive Methods in Economic Dynamics. Harvard University Press. ISBN 978-0-674-75096-8. 
• Hungerford (1980). Algebra. Springer. ISBN 978-0-387-90518-1. , first chapter on set theory.