Recursion

What is Recursion?

Any function or method which calls itself is called Recursive or Recursion. A recursive method solves a problem by calling a copy of itself to work on a smaller problem. This is called the recursion step. The recursion step can result in many more such recursive calls.

Note that it is important to ensure that the recursion must be terminates at one point of time. It will be easier for those who have seen the movie Inception. Leonardo had a dream, in that dream he had another dream, in that dream he had yet another dream, and that goes on. So it’s like there is a function called dream (), and we are just calling it in itself.

public void dream() {
   System.out.println("Inside Dreaming");
   dream();
}

Recursion is useful in solving problems which can be broken down into smaller problems of the same kind. But when it comes to solving problems using Recursion there are several things to be taken care of. Let’s take a simple example and try to understand those. Following is the pseudo code of finding factorial of a given number X using recursion.

function factorial (n) 
   if n is 0                  // base case 
      return 1 
   return n*factorial (n-1)   // break into smaller problem(s)

The following image shows how it works for factorial (5).

Capture 4
Base Case

There must be at least one base case or condition, such that, when this condition is met the function stops calling itself recursively. Any recursive method must have a terminating condition. Terminating condition is one for which the answer is already known and we just need to return that. For example, for the factorial problem, we know that factorial (0) = 1, so when x is 0 we simply return 1, otherwise we break into smaller problem i.e. find factorial of x-1. If we don’t include a Base Case, the function will keep calling itself, and ultimately will result in stack overflow. For example, the dream () function given above has no base case. If you write a code for it in any language, it will give a runtime error.

There is an upper limit to the number of recursive calls that can be made. To prevent this, make sure that your base case is reached before stack size limit exceeds.

Why Recursion?

Recursion is a useful technique borrowed from mathematics. Recursive code is generally shorter and easier to write than iterative code. Generally, loops are turned into recursive functions when they are compiled or interpreted.

Recursion is most useful for tasks that can be defined in terms of similar sub tasks. For example, sort, search, and traversal problems often have simple recursive solutions.

Recursion and Memory (Visualization)

Each recursive call makes a new copy of that method (actually only the variables) in memory. Once a method ends (that is, returns some data), the copy of that returning method is removed from memory. The recursive solutions look simple but visualization and tracing takes time. For better understanding, let us consider our factorial function. The visualization of factorial function with n=4 will look like

Capture 5
Recursion versus Iteration

While discussing recursion, the basic question that comes to mind is: which way is better? iteration or recursion? The answer to this question depends on what we are trying to do. A recursive approach mirrors the problem that we are trying to solve. A recursive approach makes it simpler to solve a problem that may not have the most obvious of answers. But, recursion adds overhead for each recursive call (needs space on the stack frame).

Recursion
  • Terminates when a base case is reached.
  • Each recursive call requires extra space on the stack frame (memory).
  • If we get infinite recursion, the program may run out of memory and result in stack overflow.
  • Solutions to some problems are easier to formulate recursively.
Iteration
  • Terminates when a condition is proven to be false.
  • Each iteration does not require extra space.
  • An infinite loop could loop forever since there is no extra memory being created.
  • Iterative solutions to a problem may not always be as obvious as a recursive solution.

Note

  • Recursive algorithms have 2 types of cases, base cases and recursive cases.
  • Every recursive function case must terminate at a base case.
  • Generally, iterative solutions are more efficient than recursive solutions [due to the overhead of function calls].
  • A recursive algorithm can be implemented without recursive function calls using a stack, but it’s usually more trouble than it’s worth. That means any problem that can be solved recursively can also be solved iteratively.
  • For some problems, there are no obvious iterative algorithms.
  • Some problems are best suited for recursive solutions while others are not. 
Example Algorithms of Recursion
  • Fibonacci Series
  • Factorial Finding
  • Towers of Hanoi
  • Merge Sort, Quick Sort
  • Divide and Conquer Algorithms
  • Binary Search
  • Tree Traversals and many Tree Problems: InOrder, PreOrder and PostOrder techniques
  • Graph Traversals: DFS [Depth First Search] and BFS [Breadth First Search]
  • Dynamic Programming Examples
  • Backtracking Algorithms 
Recursion
Scroll to top