Recursion Using Java

Recursion

 Recursion, a very  very popular topic in Computer Science. This is used in many problem solvings (eg. Dynamic programming the very first step in dynamic programming is recursion, Backtracking algorithms,merge sort,quick sort,tree traversal.....). 

The idea of recursion is to take a problem and break it into smaller problems till a point where no further breaking is possible. The case where further breaking is not possible is called "Base Cases".

Let's take an example of factorial to get a clarity on recursion.

factorial of 4 is 4*3*2*1

so when we use recursion when we enter the number 4 it will ask for factorial of  3 and fact(3) will ask for fact(2) and so on till fact(0) and it can't go further so in factorial 'zero' is base case .

 1. Java code for Factorial using recursion

int factorial(int n){
  if(n==0){
      return 1;
  }
  else{
     return n*factorial(n-1);
  }
}

invoke this method in main class and run the file

Now let's do it for fibonacci numbers

0,1,1,2,3,5,8,13,21......

fibonacci of  n is sum of (n-1) and (n-2) so recursion can be done by using fib(n-1)+fib(n-2). but we need to handle base cases if we enter zero it will call fib(-1) and fib(-2) which will throw a stackOverflowException in java. if we enter one then it will call fib(0) and fib(-1) which will also give an error. so in this case both 1 and zero are base cases.

Code for fibonacci using recursion

int fibonacci(int n){
  if(n==0){
      return 0;
  }
  else if(n==1){
      return 1;
  }
  else{
     return fibonacci(n-1)+fibonacci(n-2);
  }
 }

we can also write base cases as this for above code:

if(n<=1){

    return n;

}

Thank you.