Recursion: Fibonacci Series

Fibonacci Series generates subsequent number by adding two previous numbers. Fibonacci series starts from two numbers − F₀ & F₁. The initial values of F₀ & F₁ can be taken 0, 1 or 1, 1 respectively.

Fibonacci series satisfies the following conditions −

Fn = Fn-1 + Fn-2

So a Fibonacci series can look like this −

F₈ = 0 1 1 2 3 5 8 13

or, this −

F₈ = 1 1 2 3 5 8 13 21

For illustration purpose, fibonacci of F₈ is displayed below −

Recursion: Tower of Hanoi

Tower of Hanoi, is a mathematical puzzle which consists of three tower (pegs) and more than one rings; as depicted below −

These rings are of different sizes and stacked upon in ascending order i.e. the smaller one sits over the larger one. There are other variations of puzzle where the number of disks increase, but the tower count remains the same.

Recursion

Some computer programming languages allows a module or function to call itself. This technique is known as recursion. In recursion, a fuction α either calls itself directly or calls a function β that in turn calls the original function α. The function α is called recursive function.

Example − a function calling itself.

int function(int value) {
   if(value < 1)
      return;
   function(value - 1);
	
   printf("%d ",value);   
}