Thursday, December 10, 2009

Some general approach for solving recursive problems:

If anyone want to read an awesome super cool tutorial on recursion in BANGLA... read from Fahim Vai's page

#1: Forget about what you need to do, just think about any input, for which you know what your function should output, as you know this step, you can build up a solution for your problem. Suppose you have a function which solves a task, and you know, this task is somehow related to another similar task. So you just keep calling that function again and again thinking that, the function I'm calling will solve the problem anyhow, and the function will also say, I'll solve this problem, if you give me the result for another sub-problem first!!! Well, then you'll say, "So, why don't you use your twin-brother to solve that part?" and so on... The following example will show you how to start writing a recursive function.

Example: Think about computing n! recursively. I still don't know what and how my function will do this. And I also don't know, like what could be 5! or 7!... But nothing to worry about, I know that 0! = 1! = 1. And I also know that, n! = n(n-1)!. So I will think like that, "I will get n! from a function F, if some one gives me (n-1)!, then I'll multiply it with n and produce results". And, thus, F is the function for computing n!, so why don't I use again to get (n-1)! ? And when F tries to find out what could be the value of (n-1)!, it also stumbles at the same point, it wonders what would be the value of (n-2)!... then we tell him to use F again to get this... and this thing keeps going as long as we don't know what F actually should return for any k. In case of k = 1, as we know now F can return 1 for k = 1, and it don't need to call another F to solve anything first...

`int factorial(int n) {    // I know this, so I don't want my function to go any further...    if(n==0) return 1;    // don't bother what to do, just reuse the function...    else return n*factorial(n-1);}`

#2: What ever you can do with loops, can be done with recursions as well. A simple technique for converting recursions and loops is shown below:

Forward:
for loop:
`for(int i = 0; i < n; i++) {    // do whatever needed}`

Equivalent recursion:
`void FOR(int i, int n) {    if(i==n) return; // terminates    // do whatever needed    FOR(i+1, n); // go to next step}`

Backward:
for loop:
`for(int i = n-1; i >= 0; i -= 1) {    // do whatever needed}`

Equivalent recursion:
`void ROF(int i, int n) {    if(i==n) return; // terminates    ROF(i+1, n); // keep going to the last    // do whatever needed when returning from prev steps}`

Well, you may wonder how this is backward loop? But just think of its execution cycle, just after entering the function, it is calling itself again incrementing the value of i, and the execution routine that you have written under the function call, was paused there. From the new function it enters, it works the same way, call itself again before executing anything...Thus when you have reached the limiting condition, or the base condition, then the function stops recursion and starts returning, and the whole process can be shown as below...let n=5, and we want to print 5 4 3 2 1...code for this might be:

`void function(int i, int n) {    if(i<=n) {        function(i+1, n);        printf("%d ", i);    }}`

Explanation might look like this:
`01|call function1 with i=102|    call function2 with i=203|        call function3 with i=304|            call function4 with i=405|                call function5 with i=506|                    call function6 with i=607|                        i breaks condition, no more calls08|                    return to function509|                    print 510|                return to function411|                print 412|            return to function313|            print 314|        return to function215|        print 216|    return to function117|    print 118|return to main, done!`

Left side number shows the execution steps, so from the above program, we get, 5 4 3 2 1. So indeed it ran on reverse direction...

#3: Use the advantage of call stack. When you call functions recursively, it stays in the memory as the following picture demonstrates.

`int f(int n) {    if(n==0) return 1;    return n*f(n-1);}`

You know about stack, in a stack, you cannot remove any item unless it is the topmost. So you can consider the calling of a recursive function as a stack, where, you can't remove the memory used by f(n=3) before removing f(n=2) and so so... So, you can easily see that, the functions will hold all their variables and values until it is released. This actually serves the purpose of using an array.

#4: Be careful while using recursions. From a programming contest aspects, recursions are always best to avoid. As you've seen above, most recursions can be done using loops somehow. Recursions have a great deal of drawbacks and it most of the time extends the execution time of your program. Though recursions are very very easy to understand and they are like the first idea in many problems that pops out in mind first... they still bear the risks of exceeding memory and time limits.

Generally, in loops, all the variables are loaded at the same time which causes it a very low memory consumption and faster access to the instructions. But whenever we use recursions, each function is allotted a space at the moment it is called which requires much more time and all the internal piece of codes stored again which keeps the memory consumption rising up. As your compiler allows you a specific amount of memory (generally 32 MB) to use, you may overrun the stack limit by excessive recursive calls which causes a Stack Overflow error (a Runtime Error).

So, please think a while before writing recursions whether your program is capable of running under the imposed time and memory constraints. Generally recursions in O(lg n) are safe to use, also we may go to a O(n) recursion if n is pretty small.

#5: If the recursion tree has some overlapping branches, most of the times, what we do, is to store already computed values, so, when we meet any function which was called before, we may stop branching again and use previously computed values, which is a common technique knows as Dynamic Programming (DP), we will talk about that later as that is pretty advanced.

These techniques will be used in almost all problems when writing recursive solution. Just don't forget the definition of recursion:
Definition of recursion = See the Definition of recursion

Now try this

1. Thanks,this helped a lot.
Shafaet
16th Batch,CseDU

2. I found this blog 'accidentally' on google..
Great Blog!
It will be looking for more articles on Recursion :)

CSE DU, 16th

3. very very nice.........thank u

4. a very good learning blog,,,,many many thanks....

5. many many thanks to you, again find a way to learn

6. It was awesome!! Helped me a lot!! Your students are lucky!!

7. ধন্যবাদ !

8. Will try to make good use of it bro....

Thnax vaiya....:)

10. many many thanks vaiya

11. many many thanks vaiya

12. It's really helpful....thnx a lot vaia.... :)

13. nice blog....thanx vaiya.

14. nice blog...thanx vaiya

15. Thanks a lot vaiya

16. খুব ভালোলাগল , চালিয়ে যান

17. pretty good article!

18. Great!!!
very helpful blog.Thank you vai :)

19. Great!!!
very helpful blog.Thank you vai :)

20. Thanks Vai!!! :)

21. awesome bro .thnx

22. HI Bhai,
You have written nicely. I have a question. printf("%d ", i); line is executing after returning i=6, I mean when the break condition comes. Then is printf("%d ", i); line storing in some where? There might be 1000 line code after function(i+1, n); line. How these line execute after reaching i=6.

1. Whenever you call fucntionA from functionB, a new entry for function B is added in the call stack and the last line that you executed in functionA is also remembered. So once you finish executing functionB, you comeback to the next line you executed last in funcitonA.

If you study assembly language, it will be very clear.

23. HI Bhai,
You have written nicely. I have a question. printf("%d ", i); line is executing after returning i=6, I mean when the break condition comes. Then is printf("%d ", i); line storing in some where? There might be 1000 line code after function(i+1, n); line. How these line execute after reaching i=6.

24. thank you so much for awesome artificial written

25. thank you brother...

26. Nice post. I was checking continuously this blog and I'm impressed!
Very useful information specially the last part :
) I care for such information a lot. I was looking for this
certain information for a long time. Thank you and
best of luck.

27. Thanks for this beautiful article. Awesome really.

28. Really nice and learning post ever..