Parents : Algorithms
| Date and time note was created | $= dv.current().file.ctime |
| Date and time note was modified | $= dv.current().file.mtime |
Description
Recursion means repetition.
- To do task repeatedly until a certain known condition has reached.
- It is just a implementation difference with the iterative approach in programming for problem solving.
- In computer terms, recursion means a function repeatedly calling itself.
Why does function calls itself ?
- to take decisions of some sort.
- the decisions that function take breaks the bigger problem into smaller problem.
- and thus we have to solve a further smaller problem than solving a bigger problem.
Understanding working of recursion tells us that identification of where to recursion is the following
- Does the problem involves breaking into smaller sub-problems through decision making
- Does the problem involves some kind of repeated task or iterative task.
Each recursive approach solvable problem is also solvable using iterative approach. See: Iterative approach in programming
Recursion involves usage of two conditions
- Base case in recursion
- Recursive Condition or Recursive relation
Aditya Verma’s Course
We think of recursion as making the input smaller but it is not quite so!!
What is actually happening?
- Recursion makes the input smaller by taking atomic decisions, it is our decision that we take is making the input smaller.Thus decision making should be our primary goal and not making the input smaller
Identification of recursive problem
A [[decision space]] must be there - choices + decision must exist
- input-output method
- take at each step input and output of that stage of recursive tree , both combined represent a node in tree
- no of branches in the tree is equal to the number of choices made.
- for above example
- recursion is the sole topic that is covered in playlist
- questions done :
IBH method
- To approach recursive problem there are four methods
- Recursive tree when decision space is clearly identifiable like in the subsets problem
- Base condition - Induction - Hypothesis ,when decision space is not that clear but somehow we can see that input is getting smaller or the problem is shrinking in size
- choice diagram (dp)
- Recursive Problem using IBH:
- hypothesis : proposing and imagining what our recursion is doing for bigger problem and believing it will work for smaller further problem
- induction : the step that makes our recursion work or completes it
- base condition: stops the recursion (smallest valid input)
- for example
- print number from one to n
- hypothesis :: print(n): prints the number from 1 to n ⇒ print(n-1) ⇒prints the number from 1 t0 n-1
- induction: believing that our recursion would work for n-1 value printing and that it sub-problem our bigger problem , we can complete our recursion by printing the last number ie “n” which makes our induction step.
- base condition: as the smallest input here is 1 we stop recursion and return when the input becomes 1
- here recusive tree is a skewed recursive tree every time and hence there are less decisions made
- so thinking in terms of recursive tree would not be so quick
- hence IBH
- Beauty of recursion(flow of recursion) :
- Just changing the induction step in the recursion results in completely diff output
- for example if we want to get reverse of the numbers as from n to 1
- we can right hypothesis as the same as previous example i.e :
- print(n) works to print list from n to 1⇒print(n-1) will work for n-1 to 1
- just induction step here is written before to get n value i.e left
- base condition also remains the same
- factorial question practice
int factorial(int n){
int fact=1;
if(n==1)
return 1; // to stop recursion when the number turns 1
fact=factorial(n-1); // if the factorial works for n then it will store the result of factorial of n-1
return n*fact; // induction: multiply by n to complete the result
}
int main(){
cout<<factorial(5);
return 0;
}