Αναδρομή

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

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

• 

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

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

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

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

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

${\displaystyle n!=1\cdot 2\cdot \ldots \cdot n.}$

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

${\displaystyle 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);}

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

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

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

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

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

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

• Ο τρίτος αριθμός Φιμπονάτσι δίνεται από ${\displaystyle F_{2}=F_{1}+F_{0}=1+0=1}$ .
• Ο τέταρτος αριθμός Φιμπονάτσι δίνεται από ${\displaystyle F_{3}=F_{2}+F_{1}=1+1=2}$ .
• Ο πέμπτος αριθμός Φιμπονάτσι δίνεται από ${\displaystyle 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.