Recursion

There are two ways to approach a problem in computer science 

1. Bottom-up
2. Top-down

Bottom-up:- approach a problem from the simple case to difficult case... for example factorial of N   we start a loop from 1 to till N where product=1

product =product*1

product= product*2

product=product*3 and continue till N 

 

Top-down:- approach a problem then sub-problem and then sub problem of subvproblem until the best case ..

for example:- factorial of a number where N!-> N * (N-1)! * (N-2)! *... 1

fact(N){

if(n==1) return 1;

return n * fact(n-1)

}

where n=1 is the best case where algorithm will stop executing further.

 

Recursion:- 

Recursive shines when implementing a top-down approach

Recursion executes on call-stack where best case will the on the top

Recursion natural fits when we need to delve into multiple layers of a problem without knowing how many layers are there. e.g. find sub directories in a directory where depth is unknown 

Problems:- 

A Staircase problem:- when a person a take 1,2,3 steps at time k={1,2,3} if there are:-

N=1 then 1=> {1}

N=2 then 2=> {1,1},{2}

N=3 then 4=> {1,1,1}{1,2}{2,1}{3}

N=4 then 7=> {1,1,1,1}{1,1,2},{1,2,1},{1,3},{2,1,1},{2,2},{3,1}

what will be the answer when N can be anything e.g. any positive number ...