Function is said to be recursive if it calls itself. Recursion is used when a process is defined in terms of itself. A body of recursive function which is executed repeatedly is a type of iteration.

The difference between a recursive function and the one having a loop such as ‘while’ or ‘for’ loop is that of memory and processor overhead. Let us TRY to understand with the help of iterative and recursive functions that calculate factorial value of a number.

Iterative factorial function

Recursive factorial function

For a function that involves a loop, it is called only once. Therefore only one copy is created for all the variables used in it. Also, as function call uses stack to return function value to CALLING environment, only limited stack operations are performed.

In case of recursion, repeated calls to same function with different arguments are initiated. Hence that many copies of local variables are created in the memory and that many stack operations are needed.  

Obviously, a recursive call by function to itself causes an infinite loop. Hence recursive call is always conditional. Recursive approach provides a very concise solution to complex problem having many iterations.

In case of iterative version of factorial function, it is a straightforward case of cumulative multiplication of numbers in a range. However, in case of recursive function it is implementation of mathematical definition of factorial as below:

n! = n X (n-1)!

Here we have used factorial itself to DEFINE factorial. Such problems are ideally suited to be expressed recursively.

We can perform this CALCULATION using a loop as per following CODE:

Now we shall try to write recursive equivalent of above loop. Look at mathematical definition of factorial once again.

n!=nX(n-1)!

Substitute n with 5. The expression becomes

Let us see graphically the step by step process of computing factorial value of 5.

The diagram illustrates how successively performing factorial calculation of number by decrementing the number till it reaches 1. This involves more cost of computing.

Hence it can be seen that recursion is more expensive in terms of resource utilization. It is also difficult to write a recursive function as compared to a straightforward repetitive or iterative solution.

Having said that, recursion is sometimes preferred especially in cases where iterative solution becomes very big, complex and involves too many conditions to keep track of. There are some typical applications where we have to employ recursive solution. Traversal of binary tree structure, sorting algorithms such as heap sort, finding traversal path etc are typical applications of recursion.

On a lighter note, to be able to write a recursive solution gives a lot of satisfaction to the programmer!