Recursion in C | C - Coder's Lap

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:

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.

Remember

If the program is not designed properly, such that the function calls itself infinitely, the program will run into an infinite loop, resulting in high memory usage, and stack overflow.

What is a Stack Overflow?

A stack overflow is an undesirable condition in which a particular computer program tries to use more memory space than the call stack has available.

A popular example of recursion: Factorial numbers

#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;
}

Output

Enter a number: 5
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,

n! = n * (n-1) * (n-2) * (n-3) * (n-4) * (n-5) * ... * 3 * 2 * 1

// or simply

n! = n * (n-1)! ------ (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.

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

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.

Remember

Note that, the above code will produce the wrong output silently if the user enters some larger number.

Did you know?

Recursion is a mathematical beauty depicted as a programming feature. It is very important concept in Data Structures and Algorithm (DSA).