**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 foreve**r until **you run out of stack space** and **indicate error** about **lack of memory**, or **stack overflow**.

You may be interested in:

Data Structures and Algorithms – MCQs.

Data Structures and Algorithms Online Tests