Recursion

What is recursion?

In recursion, the solution to problem is defined as a combination of:

1. A solution to a simpler version of the problem
2. The solution to an elementary case of the problem

An example of recursion

Let's define a function Power(n):

1. If n = 1, the result is 1
2. otherwise, the result is n times Power(n - 1)

An example of double recursion

Let's define a function Fibonacci(n):

1. If n = 1 or n = 2, the result is 1
2. otherwise, the result is Fibonacci(n - 2) + Fibonacci(n - 1)

Tower of Hanoi as a double recursion

Let's define a procedure TowerOfHanoi(NumberOfDisks, OriginPeg, DestinationPeg, AuxiliaryPeg):

1. If NumberOfDisks = 1, move a disk from OriginPeg to DestinationPeg
2. otherwise,
1. TowerOfHanoi(NumberOfDisks - 1, OriginPeg, AuxiliaryPeg, DestinationPeg)
2. Move a disk from OriginPeg to DestinationPeg
3. TowerOfHanoi(NumberOfDisks - 1, AuxiliaryPeg, DestinationPeg, OriginPeg)