Recursion

Recursion is a programming technique which function calls itself , this seems strange , however it is one of the most interested and effective technique in programming.

it helps you write code in less statements and provides unique conceptual frame work to solve problems.

lets discus some problems to know how it works :

first example Triangular Numbers :

it is series like : 1,3,6,10,15,21........ etc our program should get the nth term in the series, the numbers in this series called triangular numbers due to they can be visualized as a triangle.

triangular numbers fig 1

finding the nth term using a loop see this figure :

loop adding 1+2+3+4 and so on code is easy  , a loop will add numbers from n to 0 like this

int triangle(int n)
{
int total = 0;
while(n > 0) // until n is 1
{
total = total + n; // add n (column height) to total
--n; // decrement column height
}
return total;
}

it easy enough and for sure it is fast .

before we start the recursion edition , I must emphasize on characteristics of recursion method:

1. it calls itself.
2. when calling itself , it does this to solve smaller problem.
3. there is some problems that is simple enough , that the routine can solve it with simple return statement without calling it self.

lets start solving the same problem using recursion  , the value of the nth term
can be calculated as the sum of two thing:

1.  the tallest column n .
2. the triangular of the ( n-1 )th term .

Finding the Remaining Columns:

if we know a function that can get the sum of the remaining columns we can write our triangular () as follow :

int triangle(int n)
{
return( n + sumRemainingColumns(n) ); // (incomplete version)
}

but we can notice here that the function sumRemainingColumns(n)  is just as hard as  writing triangular () , notice that the  sumRemainingColumns(n) is the sum of all columns of (n-1) ,so we could call it as follow :


int triangle(int n)
{
return( n + sumAllColumns(n-1) ); // (incomplete version)
}

but  sumAllColumns(n-1) is equals to triangular(n-1) so we can write it as follow :


int triangle(int n)
{
return( n + triangle(n-1) ); // (incomplete version)
}

great it seems like it is complete , what about running the above code , okay you will get the following results

1. it will compile with no problem
2. when running it will throw stack overflow exception ( later I'll speak about it ) if java , no output or compile error in C++.

the problem is no condition exist to make the function return it always call it self until the entire memory is full the system will throw stack overflow exception , due to the previous error we have to write piece of code to make the function return , this piece of code is called base case , our base case here is when n=1 stop adding more elements and return the result.

so final edition of the function is :

int triangle(int n)

{

if(n==1) // base case

return 1;

else

return( n + triangle(n-1) );

}

what is really happening ?
lets modify the triangular function  to show us what happen :

public static int triangle(int n)
{
System.out.println(“Entering: n=” + n);
if(n==1)
{
System.out.println(“Returning 1”);
return 1;
}
else
{
int temp = n + triangle(n-1);
System.out.println(“Returning “ + temp);
return temp;
}
}  

n=5
let's see the interaction .

Entering: n=5
Entering: n=4
Entering: n=3
Entering: n=2
Entering: n=1
Returning 1
Returning 3
Returning 6

Returning 10
Returning 15

triangular = 15.

each time triangular call itself its arguments reduced by one , again and again until the arguments equals to 1 it will return 1 , it adds the value of n it was called with to the return value from the method it called, here i emphasize the concept of stack LIFO last in first out the last call triangular ( 1 ) return first although it was the last call .


okay , here we reached to most interesting part in the post , the theoretical part, is recursion efficient ?

calling function contain certain overhead due to control transferred the location of the call to the beginning of the method, In addition, the arguments to the method and the address to which the method should return must be pushed onto an internal stack so that the method can access the argument values and know where to return.

in many times using direct methods is faster than using recursion , in addition all intermediate result should be stored in the memory which may case some memory problems.

recursion is not desirable if there exist many function calls inside the recursion methods .

finally recursion is a powerful technique and unique which can solve many problems simply using few statements code reduce.

Mathematical Induction 

Recursion is the programming equivalent of mathematical induction. Mathematical induction is a way of defining something in terms of itself Using induction, we could define the triangular numbers mathematically by saying
tri(n) = 1 if n = 1
tri(n) = n + tri(n–1) if n > 1
Defining something in terms of itself may seem circular, but in fact it’s perfectly valid (provided there’s a base case).

thanks for your valuable time , I wish you like the post , I'll feel pleasure if you ask me any questions related to the topic.

of course your comments will help improving my skills in writing and studying .

the source :Data Structures & Algorithms in Java Second Edition for Robert Lafore.

Thanks
Ahmed Ghazey.
Twitter : Ahmed Ghazey
Face book : Ahmed Ghazey
AhmedGhazey@gmail.com