Recursion in Java

Recursion:

Recursion can defined as a function calling itself until and unless it reaches to base condition and it stops. Recursion utilizes the stack segment of memory because each recursion is stored in the stack memory.

 

Why we need Recursion? 

• Recursive thinking is important in programming it help in breaking down big problems into smaller ones and easier to use.

• - When to choose recursion?

1. If you can divide the problem into similar sub problem.

2. Design an algorithm to compute nth...

3. Write the code to list the n..

4. Implement a method to compute all

5. Practice

• Prominent use of recursion in data structure such like tree and graph.

•  Interview for sure.

• It is used in many algorithms such divide and conquer, dynamic Programming and greedy.
  

Logic Behind Recursion:

1. Add method that call itself.
2. Exit from infinite loop or we can say recursive call.

    static string recursionMethod(String[] parameter){
            if (exit from condition satisfied){
                return some value;
            }else{
                recursionMethod(Modefied parameters);
            }
    }

 

Recursion vs Iteration:

Serial No.	Recursion	Iteration
1.	Recursion depends on the conditional statement	Iteration depends on conditional value
2.	Recursion is generally easy to implement.	Recursive code is sometime difficult to convert into iterative code.
3.	static int powerOfTwo(int n){ if (n == 0){ return 1; }else{ int val = 2 * powerOfTwo(n-1); return val; } }	static int powerOfTwo(int n){ var i = 0; var power = 1; while (i < n){ power = power * 2; i = i + 1; } return power; }
4.	Infinite recursion can lead to system crash.	Infinite iteration will only seems to cost CPU time.
5.	Recursion cause an overhead by utilizing memory space and processor time.	While in iteration case we don’t have such problem.
6.	Recursion is neither time efficient nor space efficient.	Iteration are basically more efficient compare to recursion.

When to use/avoid Recursion?

When to use it:

• When we can easily break down problem into similar sub-problem. 
• When we are fine with extra overhead.
• When we want quick working solution, instead of efficient one.
• When traversing tree.

How to write recursion in 3-steps?

1. Find up the recursive case or the flow.
2. Base case: The stopping criterion.
3. Unintentional case: The constrain.

Factorial.java

class Factorial{

public int factorial(int n){

if (n < 0) return -1; // Unintentional case

if (n == 1 || n == 0) return 1; // Base condition

return n * factorial(n-1); // recursive case

}

public static void main(String[] args){

Factorial recursion = new Factorial();

System.out.println(" Factorial of 6 is:" + recursion.factorial(6));

}

}

Fibonacci.java

public class Fibonacci {

public int fibonacci(int n) {

if (n < 0) return -1; // Unintentional case

if (n == 0 || n == 1) return n; // Base condition

return fibonacci(n - 2) + fibonacci(n - 1); // recursive case

}

public static void main(String[] args){

Fibonacci res = new Fibonacci();

System.out.println("Fibonnaci of 3 is: " + res.fibonacci(3));

}

}