Recursion

Recursion is just another subtle topic in any language paradigm. For some people recursion is breath taker and for some its just a handy tool for write a small code. At first Recursion seems complex to grasp, but after some practice we can master this technique very easily.

A simple definition of Recursion may be ” Recursion is a technique of defining the program in the terms of itself.”

Lets start with a simple example.

Any problem that can be subdivided in the term of itself can be solved with recursion. For example here is a recurrence formula for calculating the nth power of a ;

In this case for any value other than n = 0, we can calculate the n^th power of a by multiplying the number by (n-1)^th power of that number i.e aⁿ = a*a^n-1.

In recursion we always have to ensure a terminating condition. In absence of terminating condition the program will continue to call it self ever and ever again(forever).

In this case n=0 is terminating condition and we know its value (its 1).

Equipped with this knowledge, lets create a function for calculating n^th power of a number. For simplicity assume that the number (a) is a Integer.

Here is power function in C .

int power(int base, int degree){
 if(degree == 0){
   return 1;
 }else{
   return (base*power(base, degree-1));
 }
}

In this example for 2^nd line test for terminating condition, otherwise 5^th line calculate a*a^n-1 .