Provide an explanation of recursion, including an example.

Here we will try to explain recursion as simply as possible, without getting into the extremely theoretical and mathematical aspect of it. We want to provide a practical explanation that would be easy to understand – so think of this as an easy to understand tutorial on recursion (for beginners or “dummies”). Defining recursion is easy – any routine that calls itself is a recursive routine. You may be more familiar with the term method or function, but we use routine since that encompasses both. Although the definition of recursion is simple, using and understanding recursion is difficult – so you will need to read this article with patience and you will (hopefully) understand it.

What is recursion used for?

Recursion is best used for problems where a large task can be broken down into a repetitive “sub-task”. Because a recursive routine calls itself to perform those sub-tasks, eventually the routine will come across a sub-task that it can handle without calling itself. This is known as a base case – and it is needed to prevent the routine from calling itself over and over again without stopping. So, one can say that the base case stops the recursion.

Base cases and Recursion

In the base case, the routine does not call itself. But, when a routine does have to call itself in order to complete its sub-task, then that is known as the recursive case. So, there are 2 types of cases when using a recursive algorithm: base cases and recursive cases. This is very important to remember when using recursion, and when you are trying to solve a problem you should ask yourself: “What is my base case and what is my recursive case?”.

Example of recursion in Java – the factorial

Let’s start out with a simple example of recursion to best illustrate how it works: the factorial is probably the most commonly used example. What is a factorial? Well, any number written like this: “x!” is said to be “the factorial of x”. A factorial of a number “x” is just the product of all integers between 1 and x. So, if x is equal to the number 5, then the factorial of x would be 5*4*3*2*1, which equals 120. We could also say that the factorial of is equal to 5 multiplied by the factorial of 4, which would be 5 * 4!, or 5*4*3*2*1 So, the factorial of any number “x” could also be defined as:

x! = x * (x - 1)!

And, something else that is important to know is the fact that the factorial of 0 is equal to 1 as is the factorial of 1.

0! = 1! = 1

Breaking down the factorial to find the recursive case

Note how we defined the factorial of a number as that number multiplied by the factorial of the integer that is 1 less than the number (x * (x-1)! ). So, what we have done is essentially break the problem down into a sub-task, and in order to find the factorial of a number we just keep finding the factorials of the integers below that number and multiplying. So, the factorial of 3 is equal to 3 multiplied by the factorial of 2 and the factorial of 2 is equal to 2 multiplied by the factorial of 1. So, if we have a function called factorial that is meant to find the factorial of a given number then our code for the recursive case would look something like:


function factorial (x) {
return (x * factorial(x-1) ) ;
}

Where x is the number whose factorial we want to find. And that is what recursion is all about – finding repetitive patterns, and breaking a problem down into repetitive sub-tasks.

Finding the base case to stop the recursion in factorial

But, there is still one issue – we seem to have found a recursive case, in which the routine will call itself, but what about the base case? Remember that we must have both a recursive case and a base case. The base case is what will stop the routine from calling itself infinitely, and will stop the recursion.

Think about this – what do you think would be a good base case for this problem – when does it make sense to stop the recursion? Well, it turns out that the base case would occur when the factorial function hits a value of 1 – because at that point we know the factorial of 1 is 1, so we should stop right there. And, it doesn’t make sense to allow the function to find the factorial of numbers less than 1, since the factorial is defined for integers between x and 1.

So, here’s what the Java code for our recursive factorial method would look like:

public int factorial (int x)
{
  if (x > 1)
  {
     //recursive case:
     return factorial(x-1) * x;
  }

  else  /*base case*/
     return 1;

}

Call Stacks, Recursion, and Stack Frames

A call stack is a data structure used by the program to store information about the active subroutines (like functions in C++ or methods in Java) in a program. The main reason for having a call stack is so that the program can keep track of where a subroutine should return control to once it finishes executing. For example, suppose we have a method “CreateBox” which calls another method “CreateLine” in 4 different places. If the program has finished executing the method CreateLine, then it needs to know where in the CreateBox method it needs to return to. This is why the program uses a call stack – so that it can keep track of these details.

A call stack is composed of stack frames

A stack frame is a part of the call stack, and a new stack frame is created every time a subroutine is called. So, in our recursive Factorial method above, a new stack frame is created every time the method is called. The stack frame is used to store all of the variables for one invocation of a routine. So, remember that a call stack is basically a stack of stack frames.

Stack Frames in Recursion

A diagram of how the stack frames work in recursion will really help to clarify things – so let’s take a look at one. Lets suppose that we try to find the factorial of “3″ using the function that we created above (so “x” is equal to 3), this is what the stack frames would look like:

You can see that the first stack frame is created with x equal to 3. And then a call to Factorial(2) is made – so the first call to “Factorial(3)” does not run to completion because another call (Factorial(2)) is made before the very first call to Factorial can run to completion. A stack frame is used to “hold” the “state” of the first call to Factorial – it will store the local function variables (and their values) of the current invocation of Factorial, and it will also store the return address of the method that called it (since we are talking about the very first non-recursive invocation of Factorial, whatever routine invoked Factorial in the first place is where Factorial would return when it is completely done with everything) . Because the stack frame also stores the return address, the Factorial function knows where to return to when it finishes running.

Finally, in the 3rd stack frame, we run into our base case, which means the recursive calls are finished and then control is returned to the 2nd stack frame, where Factorial(1) * 2 is calculated to be 2, and then control is returned to the very first stack frame. Finally, our result of “6″ is returned.

Without a base case in recursion the stack overflows

What would happen if there were no base case in our example above? Well, recursive calls will be made continuously, and each time a recursive call is made a new stack frame is created. Every new stack frame created needs more memory, which then means that there is less memory on the call stack. The call stack has limited memory, which is usually determined at the start of the program – and when that limited memory is exceeded then the stack is said to overflow, which will usually result in the program crashing. So, if we did not have a base case, then the stack would overflow.

Conclusion

Hopefully, this article helped you understand recursion better. Now, if you would like to read some more interview questions that have to do with recursion then continue on in this section, or you can read one of our personal favorites right here: Recursion Interview Question.


Hiring? Job Hunting? Post a JOB or your RESUME on our JOB BOARD >>

Subscribe to our newsletter for more free interview questions.



FOLLOW Varoon Sahgal, Author of ProgrammerInterviewon

  • Gcdey

    very good explain

  • Ashraf

    Great post

  • Milan

    This is seriously some good stuff for those who keep wondering for their entire lives that how recursion works.
    Keep up the great job!

  • pratibha

    well explained ……!!!! really helped me !!!

  • Ejaz Ahmad

    only a call stack diagram solve the issue i have been facing for 2 years.
    great stuff

  • Clive

    Super, the whole notion of a 'stack frame' to store local variable values for each recursion was something I never got, I just couldn't grasp where variable values of each iteration was being stored and then returned to the invoking method…..great explanation!

  • Prince

    fANTASTIc ……really helped me…i tried to find the stuff around the net….but finally i got it here

  • taboo

    Thanks for the such nice explanation..