coffeetechgaff

A Recursion is when the method calls itself to solve a problem. The recursive solution is constructed with a base case and a recursive case. In every recursive solution, we need to have these two components. If we miss base case in our recursive solution, the method will run in never ending loop and will throw StackOverFlowError.

Base Case

A non-recursive method that terminates the recursive path. This should run first in a method to check to terminate the recursive path.

Recursive Case

A recursive method that calls itself one or multiple times to solve a problem.

The best example of recursion is to compute the factorial of a number. In mathematics, a factorial is what you get when you multiply a number by all of the integers below it. The factorial of 6 is equal to 6 * 5 * 4 * 3 * 2 * 1 = 720. We can write a recursive function for factorial as follows in java:

                      public static int factorial(int n) {
                          if (n <= 1) {
                              return 1;
                          } else {
                              return n * factorial(n - 1);
                          }
                      }

If we trace the function call of above recursive function, we can see as follows:

                      factorial(6)
                        factorial(5)
                            factorial(4)
                                factorial(3)
                                    factorial(2)
                                        factorial(1)
                                        return 1
                                    return 2*1 = 2
                                return 3*2 = 6
                            return 4*6 = 24
                        return 5*24 = 120
                      return 6*120 = 720

In this example, you see that 1 is the base case, and any integer value greater than 1 triggers the recursive case.

One challenge in implementing a recursive solution is always to make sure that the recursive process arrives at a base case. For example, if the base is never reached, the solution will continue infinitely and the program will hang. In java, this will result in a StackOverFlowError anytime the application recurses too deeply.

Following famous algorithms are using recursive strategy to solve a problem