Thursday, December 10, 2009

Attacking Recursions


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=1
02| call function2 with i=2
03| call function3 with i=3
04| call function4 with i=4
05| call function5 with i=5
06| call function6 with i=6
07| i breaks condition, no more calls
08| return to function5

09| print 5
10| return to function4

11| print 4
12| return to function3

13| print 3
14| return to function2

15| print 2
16| return to function1

17| print 1
18|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

30 comments:

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

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

    CSE DU, 16th

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

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

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

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

    ReplyDelete
  7. ধন্যবাদ !

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

    ReplyDelete
  9. It's really helpful.
    Thnax vaiya....:)

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

    ReplyDelete
  11. খুব ভালোলাগল , চালিয়ে যান

    ReplyDelete
  12. pretty good article!

    ReplyDelete
  13. Great!!!
    very helpful blog.Thank you vai :)

    ReplyDelete
  14. Great!!!
    very helpful blog.Thank you vai :)

    ReplyDelete
  15. awesome bro .thnx

    ReplyDelete
  16. 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.

    ReplyDelete
    Replies
    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.

      Delete
  17. thank you so much for awesome artificial written

    ReplyDelete