Saturday 18 February 2012

What is recursion

Simply put, recursion is when a function calls itself.
recursion is process, when a method calling itself again and again inside its body .
this is look like a never ending loop.but there is a condition which we check , if it is true then exit.
A method that calls itself is said to be recursive.
The best example of recursion is the computation of the factorial of a number.
The factorial of a number N is the product of all the whole numbers between
1 and N. for example, 3 factorial is 1×2×3, or 6. Here is how a factorial can be computed by use of a recursive method.

class Fact {
int fact(int n){
if (n==1){
return 1;
}
int result;
result= fact(n-1)*n;
return result;
}
}

class DemoClass {
public static void main (String args[]) {
Fact f =new Fact();
System.out.println("Factorial of 3 is " + f.fact(3));
}
}

Output:
Factorial of 3 is 6


in the above example a method fact is defined which is calling itself inside its body.
fact is recursive function .

now in DemoClass we calling fact(3) and execution steps are as follows:

1) first fact will check if 3==1 then return 1.
2) 3!=1, now it will call fact2(3-1)*3 (we are assigning new name fact 2 to fact for understanding)
3) now again fact will check if 2==1 then return .
4) 2!=1, now it will call fact3(2-1)*2 (we are assigning new name fact 3 to fact for understanding)
5) now again fact will check if 1==1 then return .
6) 1==1, now it will return 1 to fact2.
7) now fact2 will return 1*2=2to fact .
8) now fact2 will return 2*3=6 to DemoClass

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...