What is recursion?
Recursion is a very important concept in programming. The simplest definition of recursion is something that repeats itself. In programming terms, a recursive function or recursive algorithm is one which calls itself. In this post we will see how we can print the factorial of a given number using a recursive function.
Below is the code for recursive factorial following which is an explanation for how the recursive factorial program works.
#include<stdio.h>
int factorial ( int num )
{
if( num == 1 || num == 0 )
return 1 ;
return ( factorial ( num - 1 ) * num ) ;
}
int main ()
{
int num , ans ;
printf ( " Enter a Number: " ) ;
scanf ( "%d" , &num ) ;
if ( num < 0 )
printf ( "\nInvalid input" ) ;
else
{
ans = factorial ( num ) ;
printf ( "the factorial is:%d" , ans ) ;
}
return 0 ;
}
The function factorial() is the recursive function as it calls itself from inside its own definition. The first line of the function including the if condition with the return statement is to provide a base or an end point to the recursion. Without a base condition in any recursive algorithm, the algorithm will run endlessly, calling itself every time, with no instruction to stop or pause. The base case is the stopping condition. In the factorial program for example, it stops the recursive chain when the parameter passed to the function becomes equal to 0 or 1.
Now that we have cleared up what a base condition is in recursive functions, let's move on to the next line, which captures the essence of recursion:
return ( factorial ( num - 1 ) * num ) ;
This statement implies that whatever result is returned by calling factorial with num-1 as parameter will be returned to the calling function. If this seems confusing to you, we will follow up with an example.
Example
Let's say we want to calculate the factorial of 3. In the main program we call the factorial function with the parameter as 3 and store the result in ans variable. Now our factorial function first checks if the number is 0 or 1. It is not, so we return the value of factorial (3-1) * 3. To return this value, we will first need to calculate factorial (3-1), that is, factorial (2) is being called. Similarly, factorial (2) will call factorial (1). Now when factorial (1) is called, it satisfies the base condition that num is equal to 1. So it returns 1 (second line of function). The previous function, factorial (2) was waiting for factorial (1) so that it could return the result (factorial (1) * 2) to factorial (3). factorial (2) therefore returns (1*2) = 2 to factorial (3). factorial (3) was in turn waiting for this value (2) to return the result of factorial (2) * 3, which is now (2*3) =6. 6 is returned to the first call, that is in the main.
Hint: If you are stuck with how a factorial works, read this:
a factorial of a number is the product of all natural numbers upto that number. So a factorial of 3 = 3 * 2 * 1, a factorial of 4 = 4 * 3 * 2 * 1 and so on. Naturally, a factorial of n can be written as n * factorial of n-1, as the product of all natural numbers upto that number is equal to the product of itself and all natural numbers upto that number's predecessor. So to calculate the factorial of 5, all we need is the factorial of 4, multiply that with 5, and to know the factorial of 4, all we need is the factorial of 3, and multiply that with 4, and keep on repeating this procedure till we need to know the factorial of 1, which we know to be 1.
