Learning Goals

Introduction

Recursion

Recursion is the repeated application of a recursive procedure or definition. Example of a recursion structure:

By recursively duplicate the original pattern on the top left, we get the bottom right figure.

Another example is:

A matryoshka doll is adoll that contains inside another matryoshka doll.

We can also find recursive patterns in nature. A biologist, Lindenmayer, tried to find the mathematical patterns of different plants:

Let’s see how can we apply Recursion to algorithms.

Tower of Hanoi

The Tower of Hanoi or Towers of Hanoi is a mathematical game or puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.

The objective of the puzzle is to move the entire stack to another rod, obeying the following rules:

1. Only one disk may be moved at a time.