Recursion

Recursion/Properties of Recursion

• The same operation is performed multiple times with different inputs.

• In every step, we try to make the problem smaller.

• We mandatory need to have a base condition. Which tells the system to stop the recursion.

In case our sub-problem is similar in nature to a bigger problem, only in those kinds of cases we can use recursion else recursion

will not be efficient.

Recursion is heavily used in Data structures like Trees, Graph, Divide, and Conquer, Greedy, Dynamic Programming, etc.

Recursive Case: Case where the function recurs.

Base Case: Case where the function does not recur (exit).

Code Snippet

public class ProblemStatement {

public static void main(String[] args) {
System.out.println("function1 -> " + function1(5));
System.out.println("function2 -> " + function2(5));
System.out.println("function3 -> " + function3(5));
}

public static int function1(int num) {
if(num == 0)
return 1;
return function1(num - 1);
}

public static int function2(int num) {
if(num == 0)
return 1;
return function2(num - 1) + num;
}

public static int function3(int num) {
if(num == 0)
return 1;
return function3(num -1) + function3(num -1);
}

} 

The output will be:

function1 -> 1

function2 -> 16

function3 -> 32

Explanation:

function1(0)	Return – 1
function1(1)	Return – 1
function1(2)	Return – 1
function1(3)	Return – 1
function1(4)	Return – 1
function1(5)	Return – 1

function2(0) + 1	Return – 1 + 1 = 2
function2(1) + 2	Return – 2 + 2 = 4
function2(2) + 3	Return – 4 + 3 = 7
function2(3) + 4	Return – 7 + 4 = 11
function2(4) + 5	Return – 11 + 5 = 16
function2(5)	Return – 16

function3(0) + function3(0)	Return – 1 + 1 = 2
function3(1) + function3(1)	Return – 2 + 2 = 4
function3(2) + function3(2)	Return – 4 + 4 = 8
function3(3) + function3(3)	Return – 8 + 8 = 16
function3(4) + function3(4)	Return – 16 + 16 = 32
function3(5)	Return – 32