Recursion in C
Continuing the concepts of functions, in this chapter we will learn about recursion.
What is Recursion?
Recursive function is a function that calls itself, under certain conditions. The process is called recursion. The concept is quite similar to the concept of loops.
Recursion can be depicted by the following format:
Recursion can be depicted by the following format:
return_type function_name (parameter_list) {
// function body
if (certain condition) {
return return_value;
}
return function_name (parameter_list);
}
We can see that the function calls itself, as the return value is the call to itself, if certain condition is false. If the condition is true, the function returns the return value, which won't be the call to itself.
// function body
if (certain condition) {
return return_value;
}
return function_name (parameter_list);
}
A popular example of recursion: Factorial numbers
C
#include <stdio.h>
#include <math.h>
unsigned long long factorial (unsigned long long n) {
if (n == 0) {
return 1;
}
return n * factorial (n - 1);
}
int main () {
int n;
printf ("Enter a number: ");
scanf ("%d", &n);
printf ("Factorial of %d is %llu", n, factorial (n));
return 0;
}
#include <math.h>
unsigned long long factorial (unsigned long long n) {
if (n == 0) {
return 1;
}
return n * factorial (n - 1);
}
int main () {
int n;
printf ("Enter a number: ");
scanf ("%d", &n);
printf ("Factorial of %d is %llu", n, factorial (n));
return 0;
}
Output
Enter a number: 5
Factorial of 5 is 120
Factorial of 5 is 120
Explanation
To understand this, we will need to understand what actually is factorial.
We know, 5! = 5 * 4 * 3 * 2 * 1 = 120.
Which means,
First of all, let me explain why unsigned long long is used. It is because, we will encounter very large numbers while calculating factorial. Hence, we used unsigned long long to atleast calculate the factorial upto 20!
Now, let us understand the program. We have a function factorial which takes an unsigned long long parameter n.
At first, the function main is executed, and an input is taken and stored in n. Now, function factorial is passed as an argument to printf, with format specifier for unsigned long long as %llu. Then the function factorial is called with n as parameter.
Now, the function factorial is called recursively. For the first time, it is called with n as an argument. Then, until n is not equal to 0, it is called again with a number one less than the argument n.
The functions to be evaluated are stacked in a stack. The stack is a data structure that stores the values of the function calls. It is stored in last-in-first-out (LIFO) manner.
Stack in factorial
Let's understand the above code for n = 5.
Initially, factorial(5) is called. Since, 5 != 0, the function returns
In the above code, we have, if n is equal to 0, then the function returns 1. This is because, the factorial of 0 is 1, mathematically.
We know, 5! = 5 * 4 * 3 * 2 * 1 = 120.
Which means,
n! = n * (n-1) * (n-2) * (n-3) * (n-4) * (n-5) * ... * 3 * 2 * 1
This program is based on the equation (1) above. We can clearly see, the mathematical function of factorial is n! = n * (n-1)! is also recursive. This is known as the recurrence relation.
// or simply
n! = n * (n-1)! ------ (1)
First of all, let me explain why unsigned long long is used. It is because, we will encounter very large numbers while calculating factorial. Hence, we used unsigned long long to atleast calculate the factorial upto 20!
Now, let us understand the program. We have a function factorial which takes an unsigned long long parameter n.
At first, the function main is executed, and an input is taken and stored in n. Now, function factorial is passed as an argument to printf, with format specifier for unsigned long long as %llu. Then the function factorial is called with n as parameter.
Now, the function factorial is called recursively. For the first time, it is called with n as an argument. Then, until n is not equal to 0, it is called again with a number one less than the argument n.
The functions to be evaluated are stacked in a stack. The stack is a data structure that stores the values of the function calls. It is stored in last-in-first-out (LIFO) manner.
![Stack in factorial](/media/course/c/stack.png)
Let's understand the above code for n = 5.
Initially, factorial(5) is called. Since, 5 != 0, the function returns
5 * factorial(4)
Then, factorial(4) is called. Since, 4 != 0, the function returns
5 * 4 * factorial(3)
Then, factorial(3) is called. Since, 3 != 0, the function returns
5 * 4 * 3 * factorial(2)
Then, factorial(2) is called. Since, 2 != 0, the function returns
5 * 4 * 3 * 2 * factorial(1)
Then, factorial(1) is called. Since, 1 != 0, the function returns
5 * 4 * 3 * 2 * 1 * factorial(0)
Then, factorial(0) is called. Since, 0 == 0, the function returns
5 * 4 * 3 * 2 * 1 * 1
Hence, the final value of factorial(5) is 120.
In the above code, we have, if n is equal to 0, then the function returns 1. This is because, the factorial of 0 is 1, mathematically.