hello, im not understand concept of recursion function and the uses...have anybody explain to me...
second how to write a recursive version of function to determine if an input is prime...
hello, im not understand concept of recursion function and the uses...have anybody explain to me...
second how to write a recursive version of function to determine if an input is prime...
Recursive Function :
By definition : A recursive function is a function that either calls itself , or calls another function which in-turn calls itself.
In rather simple words it means a function that performs repetitive action until a goal is reached.
Recursive Functions basically have 2 cases:
1. A specific condition ending the condition.
2. A repetitive process of calling itself.
For example You could consider the most basic of all recursive functions :
The Factorial Program :
In math:
n!= n*(n-1)*(n-2)*.............2*1
So a simple function in C++ in a non repetative fashion would be
long factorial (unsigned int x )
{
long val=1;
for( int i= x; i >0; i-- )
val*=i;
return val;
}
This will probably do the job. But since we know that
n!= n* (n-1)!
Now, we could now write a function that would be recursive to find the factorial of an integer n.
CASES:
Now lets get back to what the specific case during the function execution will be:
We know that the base condition in factorials is '0' .
and
0!=1
And the repetitive part would be
n!= n * (n-1)!
So we could code out something like this.
long factorial ( unsigned int x )
{
if (x== 0 ){
//Check for base conditional case.
return 1;
//If thats true return basic condition answer
}
else{
return x * factorial (x-1); //Else continue the cyclic/repetitive step.
}
}
The inner working of the recursive factorial explained :
Consider we wish to find the factorial of a number 5.
- First x = 5;
- in the if statement it gets checked if 5== 0,
- Because its false , we now will have the else statement executed.
- '5' is kept in the memory. and now the computer in-turn tries to calculate factorial (4);
'5' is kept in memory and put at halt until factorial of (4) is got.
then in the next step.
'4' is kept in the memory and we await result for factorial (3).
.................................
................................
once we get to factorial (0 ) .. the condition is true and 1 is returned.
now factorial (1) is computed to 1*1
factorial 2 is computed to 2*1*1.
so on.......
we get to factorial 5 computed to 5*4*3*2*1*1
---------------------------------------------------------------------
The same is with more recursive functions.
All you need to identify is a specific condition which marks the end to the recursive function and secondly the looping mechanism calling itself.
Note: The looping mechanism should always get relatively closer to the basic condition.
Hope this helps you understand recursive functions better.