This post was there with me for quite some time - but couldn't complete it for almost six months. At last its done! Hope you will enjoy it.
One should read the dialog in Lewis Carroll writing or Godel, Escher, Bach.
Here is the dialog that I have referred to from Wikipedia.
[Achilles and Tortoise meet at a coffee shop after a long break.]
Achilles: It has been long that we have met.
Tortoise: Yeah! But the good thing is that, here we are together; once again. So what have you been doing all these days?
Achilles: Nothing!
Tortoise: So it must have been boring for you.
Achilles: Oh no, no! It was not boring at all. I have learnt programming of late and I was playing with couple of programming languages. Like I was figuring out how I can model all that we have discussed previously. Especially the one that you and I got into endless thousand page ranting on with A, B, C … to prove Z. You remember?
Tortoise: Yes, I do in fact! That was a fun! I hope you understand that it is very difficult to prove that uh!
Achilles: You should learn programming and you will come to know that what you did was an infinite loop. You would have understood the loop will go on and on.
Tortoise: Loop?
Achilles: Yes my dear friend – loop.
Tortoise: So what is this “Loop” is all about?
[Achilles smiles and continues, after a sip of cappuccino]
Achilles: You see loops are very simple. If you want to do something repeatedly you just say that.
Tortoise: Elaborate please.
Achilles: Like say you want to add all the integers from 1 to 10. You start a loop, let x equals to 1 and sum equals 0. Add sum and x and assign the result to sum, after that you increase x by 1 and do this till x is less than 11; you see you want to add all integers till 10. Pretty simple, huh?
Code snippet:
int sum = 0;
for (int x = 0; x < 11 ; x++) {
sum += x;
}
Tortoise: Fine! But looks odd to me!
Achilles: Why? Is there anything wrong?
Tortoise: You know my friend; you have learnt a programming language but I am a little handicapped with that, i.e. “programming language”, but I feel I have a different way of understanding this one.
Achilles: How?
Tortoise: Do you know the mathematical concept of function? Like F(x, y) = x + y?
Achilles: Yes I do.
Tortoise: Great! We can represent the solution like the following function in mathematics:
F(x, y) = y + x; if x = 10 … (RULE 1)
= F(x+1, y+x); 1 <= x <= 9 … (RULE 2)
O mighty Achilles! How will you write this in your programming language?
Achilles: I see! Let me tell you how to do that in programming language. [Achilles shows the code snippet]
public int sum(int x,int y) {
if (x == 10) {
return y+x;
} else {
return sum(x+1,y+x);
}
}
Achilles: I knew this from my advance classes in programming – it is called recursion. But how do you explain this.
Tortoise: Very simple my friend! The RULE 1 says that if the variable x is equal to 10 you are going to produce the summation of x and sum as result else it will keep on calling itself with an incremented value of x and summation of x and the y variables. It’s very basic math you see.
Achilles: But you need to have a termination rule to complete the task! How would you explain that A, B and Z proposition problem with recursion? It was an endless loop right? No terminating condition.
Tortoise: Really? But I knew that there was a terminating condition there too! It was your last proposition. If I would have accepted it – the so called loop was over. But I did not accept it I just kept on adding one more layer in between the final and penultimate statement. So the final statement was the terminating condition.
Achilles: But as you see now, in this example we have a terminating condition as 10…
Tortoise: That need not to be 10, we can introduce a third variable say z or we can call it terminator if you like it. We can rewrite the function definition as follows:
F(x, y, z) = y + x; if x = z … (RULE 1)
= F(x+1, y+x, z); 1 <= x <= 9 … (RULE 2)
And this one should work for any integer value of z – isn’t it?
Achilles: Yes it would and the program would look like:
public int sum(int x, int y, int z) {
if (x == z) {
return y+x;
} else {
return sum(x+1, y+x, z);
}
}
And we could invoke this with something like: sum(1, 0, 10) and it works. But, tortoise, it is still does not create an infinite loop like what you had created.
Tortoise: Yes, Achilles it can but needs a little imagination. I created something like this:
F(x, y, z) = y + x; if x = z … (RULE 1)
= F(x+1, y+x, x+2); 1 <= x <= 9 … (RULE 2)
Look closely, warrior; I have introduced a never reaching fallacy in the RULE 2 function. Instead of z I am passing x+2 as the last argument. This will prevent the condition for RULE 1 and it will remain like that illusive last statement.
[Tortoise paused for a moment]
Tortoise: Now you see it!
Achilles: Yes.
Tortoise: I am going home – would you like to join?
Achilles: No!
[Tortoise leaves slowly. Achilles looks at the paper and nods his head in disbelieve.]
Achilles: Waiter! Get me a java green please.
The java code for this never ending recursion would look like:
public class Recursionist {
/**
* @param args
*/
public static void main(String[] args) {
Recursionist r = new Recursionist();
System.out.println(r.sum(1,0,100));
}
public int sum(int x,int sum,int termination) {
if (x == termination) {
return sum+x;
} else {
return sum(x+1,sum+x,x+2);
}
}
}
OUTPUT: A stack overflow exception - at some point of time I gusse.
Moreover you do not do all these for Arithmetic Progression you just use the formula.
No comments:
Post a Comment