Recursion and Recurrence Relation

Recursion  and Recurrence Relation 

Recursion:

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

Example:

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

A recurrence is an equation or inequality that describes a function in terms of its values on smaller inputs. To solve a Recurrence Relation means to obtain a function defined on the natural numbers that satisfy the recurrence.

3 methods to Solve Recurrence Relation 

1. Substitution method
2. Master method
3. Recursion Tree Method

Substitution: 

It consists of two main steps:

• Guess the Solution.
• Use the mathematical induction to find the boundary condition and shows that the guess is correct.

Recursion Tree Method

It is a pictorial representation of an iteration method which is in the form of a tree where at each level nodes are expanded.

 In general, we consider the second term in recurrence as root.

It is useful when the divide & Conquer algorithm is used.