What is Recursion...? Recursion is used to make our complex codings simpler. Just think about a loop. Let's think about a function which is used to find it's factorial. This is how we do it normally. int fact(int no) { int facNo = 1; for(int i=1; i<=no; i++) { facNo = facNo*i; } return facNo; } Let's think about 5!. We know that 5! is equal to 5 * 4!. If we know 4!, we can get the value easily. But we have don't know 4! yet. 4! also can be written as 4 * 3!. So if we know 3! , we can find 4! . this cycle will go as follows. 5! = 5 * 4! 4! = 4 * 3! 3! = 3 * 2! 2! = 2 * 1! 1! = 1 * 0!. Here we can't go on after 0!. But we know 0! is equal to 1. So now we can go backwards. 0! = 1 1! = 1 * 1 = 1 2! = 2 * 1 = 2 3! = 3 * 2 = 6 4! = 4 * 6 = 24 5! = 5 * 24 = 120 So now we have the answer 120. But how we can apply this to our coding..? We can see that in this method, we we multiplied our current value with a previous result (5 * 24 where 24 is came from previous step). So we have to implement a simple multiplication in our coding. But how do we get the previous result..? We can call the same function again inside the function. facNo = no * fact(no-1); Will this work..? We are going to call the function inside the same function. This will work. Because when the function is called, It will act as a different function. So we can implement following function with less number of coding. int fact(int no) { int facNo = 1; facNo = facNo * fact(no-1); return facNo; } It will not be easy to understand this program just by looking at this. Do a dry run on your own. Then you will be able to understand this properly. If you do a dry run, You will recognize an error...! this function will never end. This will run untill your computer get stucked. Because we have not inserted the value of 0! here. So this will not stop at 0!. We have to add a small modification in order to make this stop at 0!. We have to call the function only when no is not equal to 0. If it is equal to 0, we have to return 1 which is the value of 0!. So we check whether the value is equal to 0 or not before performing facNo = facNo * fact(no-1); step. int fact(int no) { if (no == 0) return 1; else { int facNo = 1; facNo = facNo * fact(no-1); return facNo; } } int fact(int no) { if (no == 0) return 1; else return (no * fact(no-1)); } Since this is a small function, you will not find much difference between recursion & iteration(which refers to our normal way). But when the function is very complex, there will be a big difference. In recursion , there are 2 main cases that you have to concentrate. 1. Base case / Anchor Statement 2. Recursive Relationship Base case is the step that we have to stop our function. In the above function, it was 0!. This is the place that we can not simplify the function further. And we know the actual value of base case. Recursive Relationship is the step that we call the function again. This step will act as a loop. In above case, this was facNo = facNo * fact(no-1); And also in the Recursion, we must change the value of parameter that we are passing. Else this will run an infinite number of times. In the above case, in the function calling we have called it as no-1 which will reduce the value of no step by step. |
< Back . |
