Recursion In C++

This is another favorite topic in interviews and in question papers.

What is recursion? Recursion comes from the word ‘to recur’ which means happening repeatedly over and over again.

In programming we have recursive functions and they are functions that keep repeating themselves. How do they repeat themselves? Well, it’s like the function keeps calling itself till an end occurs.

It might seem really funny to think of a function calling itself but this is what exactly happens.

The best example for recursion is to calculate factorials. In the last program We wrote a function to find the factorial of a number using ‘for’ loop. We’ll now see how to do the same using recursion.

Remember to read the program just like the compiler would read it; otherwise you’re bound to get confused.

Out put of the program

First of all, the function fact ( ) is the recursive function here. Why? Check out the function body and you’ll see that this function calls itself. So, let’s read through the function just like the compiler would.

For understanding purpose, let’s assume that we want to find the factorial of 4.

Now num=4 and n=4.

The compiler enters into the recursive function and calculates value of ‘result’.

result = 4* fact (3);

what does fact(3) mean? ‘Fact’ is a function and hence the function is being called with a different argument value.

The value returned by the function is ‘result’ (which is 4*fact(3)). But there is another function called in this returned value.

So the program tries to calculate fact(3). When calculating fact(3), it again calculates the value of ‘result’. Now,

result=3*fact(2);

This value is returned and your actual expression in the computer would be 4*3*fact(2). What next? Calculate fact(2) and this leads to:

result=2*fact(1);

Hence the expression in the computer will be 4*3*2*fact(1). The program calculates fact(1). When the value of ‘n’ is 1, we have specified an ‘if’ condition that says:

return 1;

Hence 1 is returned for fact (1) and the entire expression now is: 4*3*2*1 and the compiler produces the result by multiplying all the terms.

If you don’t give the ‘if’ condition the recursive nature will never stop and it will lead to problems.

Remember: When using recursive functions make sure that there is a way for the function to stop itself from infinitely repeating itself.

Will it repeat infinitely? When using recursion there are chances for stack overflow. Stack is a special portion of memory where the computer stores temporary values.

For example when a computer encounters a function call, it has to store the current location before going to the function.

When the function is executed, the program will return back to the original position and continue the program execution. In recursive functions, there are chances for the stack getting used up quickly. That’s what is stack overflow.

Anyway, there isn’t much advantage of using recursion but there may be some cases where you feel that recursion might make the coding easier. But be very careful while using recursion.

Remember: Any C++ function can be made recursive. What about main( )? It is also a C++ function. Well,main ( ) is the one function which CANNOT be made recursive.