Recursive function to find the factorial of a positive number:
unsigned long int rfact(unsigned long int num)
{
if (num==0)
return 1;
else
return n*rfact(n-1);
}
In the above function (num==0), is the base condition. When this condition is true then the recursive call is terminated. In the recursive call you can observe that every time the actual parameter value is changed. It is necessary to reach to the base condition. Suppose that the recursive function is called with a parameter 4. Then the function will return the value of the expression 4*rfact(3); it means the function rfact() is called i.e. recursion. So, the function will return the value only after getting the value of rfact() is again called with parameter 2. So, till the base condition is satisfied the same function is called again by again by changing the parameter. When the parameter is 0 for the rfact(), the call terminates by returning 1. Then one by one all the function calls will be terminated in the reverse order of their calls. This is called as backtracking. So the call rfact(0) returns 1, rfact(1) also returns 1, rfact(2) returns 2, rfact(3) returns 6, rfact(4) returns 24. 24 is the final value returned by the first function call. So the factorial value of 4 is 24.
Recursive function to find ‘gcd’ of two positive numbers:
int rgcd(int a, intb)
{
if (a%b=0)
return b;
else
rgcd(b, a%b);
}
unsigned long int rfact(unsigned long int num)
{
if (num==0)
return 1;
else
return n*rfact(n-1);
}
In the above function (num==0), is the base condition. When this condition is true then the recursive call is terminated. In the recursive call you can observe that every time the actual parameter value is changed. It is necessary to reach to the base condition. Suppose that the recursive function is called with a parameter 4. Then the function will return the value of the expression 4*rfact(3); it means the function rfact() is called i.e. recursion. So, the function will return the value only after getting the value of rfact() is again called with parameter 2. So, till the base condition is satisfied the same function is called again by again by changing the parameter. When the parameter is 0 for the rfact(), the call terminates by returning 1. Then one by one all the function calls will be terminated in the reverse order of their calls. This is called as backtracking. So the call rfact(0) returns 1, rfact(1) also returns 1, rfact(2) returns 2, rfact(3) returns 6, rfact(4) returns 24. 24 is the final value returned by the first function call. So the factorial value of 4 is 24.
Recursive function to find ‘gcd’ of two positive numbers:
int rgcd(int a, intb)
{
if (a%b=0)
return b;
else
rgcd(b, a%b);
}