Recursion

Recursion: A function that calls itself. 

    Recursion is appropriate when a problem can be solved by dividing it into sub-problems, and to achieve the solution we use the same algorithm for sub-problems.

Recursion will terminate when the base case is true.

for example

    x=5

    f(0)=1

    f(x)=f(x-1)+3

    here we need to find f(5) value by using function expression

According mathematics it is a function. 

solution:  when we call f(5) function, it calls f(5-1)+3 => f(4)+3

Again, we have f(x) function here, and x value changed to 4. f(4)=f(4-1)+3 => f(3)+3 

This continues until the x value reaches to 0.

f(3)=f(2)+3

f(2)=f(1)+3

f(1)=f(0)+3

f(0)=1

if we back track the problem f(1)=1+3=4; f(2)=f(1)+3=4+3=7; f(3)=f(2)+3=7+3=10; f(4)=f(3)+3=10+3=13; f(5)=f(4)+3=13+3=16

=> f(5)=(((((f(0)+3)+3)+3)+3)+3)

:.  f(5)=16

Here, the f(x) calling itself until it reaches to break/terminate point.

Easy recursion problems

=> Fibbonacci series

=> number is palindrome or not

=> GCD

=> String length using recursion, etc.

Medium recursion problems:

=> subsets of string/list

=> Combinations of elements, etc.

Hard recursion problem

=> N queen problem

finding all possible subsets of a list

input:

Output