Recursion is a very important and powerful idea in computer science and algorithms. A problem can be solved recursively if it can be reduced into smaller similar problems. Recursion is usually implemented by creating **a function which calls itself** from within its own code.

Let us understand this by a simple example of calculating n! (read as '**n factorial**').

**Factorial **of a positive integer n, denoted by n!, is the product of all positive integers less than or equal to n. For example, the value of 4! is 4\times3\times2\times1 = 24 . Note that the value of 0! is 1, according to the convention for an empty product.

We can write n! as :

This can be written as the following (for n > 0):

For n=0, we define n! = 1.

Let's see how we can implement a function factorial(n) which calculates n!

type=codeblock|id=recursion_factorial|autocreate=cppint factorial(int n) {if (n == 0) return 1;return n * factorial(n-1); // <== recursion}int main() {cout << "Factorial of 3 is " << factorial(3) << endl;cout << "Factorial of 1 is " << factorial(1) << endl;return 0;}

Output:

Factorial of 3 is 6Factorial of 1 is 1

The factorial() function above implements the equations we saw earlier quite directly. We'll take a detailed look at what happens when factorial(3) is called in a bit. First, we want to draw your attention to the following points:

- In the code above, the function factorial() calls itself in its definition (line 6). This process is called recursion and the function factorial() is a
*recursive function*. - The case for n=0 is called a
**base case**. Base case is the condition for which we already know the solution (usually a small / trivial case) so as to terminate the recursive calls. Every recursive function must have a base case, otherwise the recursive function will keep calling itself indefinitely forever.

Note: If you are thinking that the above factorial() function can also be implemented iteratively using a single for-loop, then what's the need of recursion. The main advantage of recursion is that it often simplifies the code, and we will see an example at the end of this tutorial.