Up: .

# Recursion

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.

## Contents

- General
- 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
- Exponentiation
- Exponentiation

Faster exponentiation

A comparison