Within a function body, if the function calls itself, the mechanism is known as ‘Recursion’ and the function is known as ‘Recursive function’.
Now let us study this mechanism in detail and understand how it works.
• As we see in this mechanism, a chaining of function calls occurs, so it is necessary for a recursive function to stop somewhere or it will result into infinite callings. So the most important thing to remember in this mechanism is that every “recursive function” should have a terminating condition.
• Let us take a very simple example of calculating factorial of a number, which we all know is computed using this formula 5! = 5*4*3*2*1
• First, we will write a non – recursive or iterative function for this.
Write a program to find the factorial of a number
#include <stdio.h>
main ()
{
int n, factorial;
int fact(int);
printf (“Enter any number:\n” );
scanf ("%d", &n);
factorial = fact ( n); /* function call */
printf (“Factorial is %d\n”, factorial);
}
/* Non recursive function of factorial */
int fact (int n)
{
int res = 1, i;
for (i = n; i >= 1; i--)
res = res * i;
return (res);
}
OUTPUT
Enter any number: 5
Factorial is 120
How does it work?
Suppose we call this function with n = 5
Iterations:
1. i= 5 res = 1*5 = 5
2. i= 4 res = 5*4 = 20
3. i= 3 res = 20*4 = 60
4. i= 2 res = 60*2 = 120
5. i= 1 res = 120*1 = 120
Now let us write this function recursively. Before writing any function recursively, we first have to examine the problem, that it can be implemented through recursion.
For instance, we know n! = n* (n − 1)! (Mathematical formula)
Or fact (n) = n*fact (n-1)
Or fact (5) = 5*fact (4)
That means this function calls itself but with the value of argument decreased by ‘1’.
Modify the program using recursion.
/*Program to find factorial using recursion*/
#include<stdio.h>
main()
{
int n, factorial;
int fact(int);
printf("Enter any number: \n" );
scanf("%d",&n);
factorial = fact(n); /*Function call */
printf ("Factorial is %d\n", factorial); }
/* Recursive function of factorial */
int fact(int n)
{
int res;
if(n == 1) /* Terminating condition */
return(1);
else
res = n*fact(n-1); /* Recursive call */
return(res);
}
OUTPUT
Enter any number: 5
Factorial is 120
How does it work?
Suppose we will call this function with n = 5
Thus a recursive function first proceeds towards the innermost condition, which is the termination condition, and then returns with the value to the outermost call and produces the result with the values from the previous return.
Note: This mechanism applies only to those problems, which repeats itself. These types of problems can be implemented either through loops or recursive functions, which one is better understood to you.