Up: .


Let's explore the concepts of recursion and recurrences. Recursion often allows easily expressing complex procedure, with often impressive results. We examine recursion through two specific examples: the Towers of Hanoi puzzle and exponentiation.

This tutorial begins with a description of the Towers of Hanoi puzzle.


What is recursion?
What is a recurrence?
Aside: Avoiding circularity
Aside: Fibonacci numbers
Aside: Other recursion pages
Towers of Hanoi
About the Towers of Hanoi
Aside: Historical background
Writing a Towers of Hanoi program
Tracing our program
Will the world end soon?
A closed-form solution
Faster exponentiation
A comparison