Overview of Recursion

PropellerAds

Overview of Recursion:

A function must be able to call itself.

For example, let us consider the function factr() shown below, which computers the factorial of an integer.

#include < stdio.h >
int factorial (int);
main()
{
int num, fact;
printf (“Enter a positive integer value: ");
scanf (“%d”, &num);
fact = factorial (num);
printf ("\n Factorial of %d =%5d\n", num, fact);
}
int factorial (int n)
{
int result;
if (n == 0)
return (1);
else
result = n * factorial (n-1);
return (result);
}

A non-recursive or iterative version for finding the factorial is as follows:

factorial (int n) 
{
int i, result = 1;
if (n == 0)

return (result);
else
{
for (i=1; i<=n; i++)
result = result * i;
}
return (result);
}

The operation of the non-recursive version is clear as it uses a loop starting at 1 and ending at the target value and progressively multiplies each number by the moving product.

When a function calls itself, new local variables and parameters are allocated storage on the stack and the function code is executed with these new variables from the start. A recursive call does not make a new copy of the function. Only the arguments and variables are new. As each recursive call returns, the old local variables and parameters are removed from the stack and execution resumes at the point of the function call inside the function.

When writing recursive functions, you must have a exit condition somewhere to force the function to return without the recursive call being executed. If you do not have an exit condition, the recursive function will recurse forever until you run out of stack space and indicate error about lack of memory, or stack overflow.

Try Now Data Structure MCQs
Data structure-Recursion MCQ Based Online Test