Recursion is shit.

Unless you want your programs to segfault, then it's okay.

>>1

Recursion makes the routine very concise and proof of correctness can be established very easily via induction on the number of recursive calls. Tail call elimination can be used to achieve the same efficiency and memory usage as plain iteration, but there is the freedom to jump to other modular functions. Using recursive calls that use stack space when it is not necessary is bad practice, and will likely cause a stack overflow for reasonable invocations. But it is ok as long as the amount of stack space used is the same as the amount a loop would require, either by allocating an array or using a stack of its own.

Since when did /prog/ become so filled with ignoramuses like >>1.

>>2
Recursion makes the routine very concise and proof of correctness can be established very easily via induction on the number of recursive calls.

You're still a dumbass jew with no possible future as a computer programmer. With that, you might want to google the term 'recurrence relation'.

I'm with >>5, recursion is awesome!

>>1
HAhaHAhaHAha

No.

>>4
yeah, nevermind, I should have said by induction on the value of a function applied to the arguments (like the length of a list, or height of a tree or something). Trying to do it by induction on the number of recursive calls isn't going to be very successful if there is infinite recursion, although it wouldn't be correct in that case, so you wouldn't be able to prove correctness. But the idea is that every recursive call brings you closer to the solution. So you first prove that the trivial case is correct, and that then given that the next recursive calls will solve their subproblems, you prove that the calling instance is correct.

>>7
lol

>>8
^{i don't get it}

>>7

yeah, nevermind, I should have said by induction on the value of a function applied to the arguments (like the length of a list, or height of a tree or something).

No, that's still incorrect.

Trying to do it by induction on the number of recursive calls isn't going to be very successful if there is infinite recursion,

Yes it will. I believe this is called functional programming you etard.

But the idea is that every recursive call brings you closer to the solution.

No. That is called approximation, not recursion.

>>10

I don't think you understand what I'm talking about, so here is an example:


MERGE_SORT(array A)
  if (A is empty)
    return the empty array.
  else
    return MERGE(MERGE_SORT(left half of A), MERGE_SORT(right half of A))

Where MERGE(A,B) has been proven to generate a sorted array if A and B are both sorted. With this, you prove that MERGE_SORT is correct, by induction on the length of A.

Base case: Suppose that the length of A is zero.
Then the empty array is returned which is sorted. If the length of A is one, then an array of its only elements is returned, and any array of length one is sorted.

Let n > 1 and suppose that MERGE_SORT returns a sorted array, for all input arrays that have length less than n, and let A be an array of length n. The left and right half of A must both have length strictly less than n. So MERGE_SORT applied to each half will yield two sorted arrays. MERGE is then applied to two sorted arrays, and will yield a sorted array, which is then returned from MERGE_SORT(A). By induction, we are done.

Do you see how this method can be applied in general? You prove the correctness of a function be first proving all of the calls it makes yield correct results, and then you rely on that correctness to establish the correctness of the function itself.

>>11
The formal name that you're looking for is a recurrence relation you fucking twit. To put this in terms that your dumbass can understand, you convert the recursive function to it's corresponding recurrence relation by induction.

Nowhere along the line do you use the actual recursive function itself. For more info, I would encourage you to actually get a decent book on data structures, and yes, actually read it.

>>12
*you convert the recursive function to its corresponding recurrence relation and then prove the recurrence relation by using induction*

>>11
You prove the correctness of a function be first proving all of the calls it makes yield correct results
No.

Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers (positive integers). It is done by proving that the first statement in the infinite sequence of statements is true, and then proving that if any one statement in the infinite sequence of statements is true, then so is the next one. -- http://en.wikipedia.org/wiki/Mathematical_induction

Please get out and study for a while before posting again.

>>14

I was outlining a way of thinking for going about proving the correctness of a routine. Induction is handy when that routine begins to call itself, or calls functions that call itself, with parameters that decrease with respect to some kind of measurement of size (a function that maps it to the natural numbers). You provided the correct definition of induction, but if you can't see it in the merge sort example, you don't know it.

>>12

I use recursive function to denote a function that satisfies a relevant recurrence relation. Deal with it.

>>16
And that is totally incorrect. The two aren't the same. The fact that you think they are makes you not only clueless, but also a dumbass. Again, I think you need to actually read and study an undergrad data structures book.

>>17

Then please define a recursive function in the context that you are thinking of.

The only thing under this disambiguation list that seems appropriate is recurrence relation, and recursion in terms of programming.
http://en.wikipedia.org/wiki/Recursive_function

>>18
Huh? I have my undegrad data structures book right in front of me. This book, like most data structures books, takes a recursive function, then converts it to a recurrence relation. The proof of correctness is proving the recurrence relation by induction.

Again, you're stupid. And again, you have no possible future as a computer progrmmer.

>>19

And you are unable to define a recursive function. Why do you make a big deal about people using terms in a way different from what you are used to when you can't even define the terms?

>>20
Because a recursive function and a recurrence relations are two different fuckig things you moron. One use of a recurrence relation is to prove the correctness of a recursive function.

With that, let I'm going to recite how my undergrad data structure book defines a recursive function you stupid annoying fucker...

"A method that calls itself is a recursive method. The invocation is a recursive call ora recursive invocation.

>>20
And later on in the same chapter...

"When n is 1, countDown displays 1. This is the base case and requires constant amount of time. When n > 1, the method requires a constant amoutn of time for both the println statement and the comparison. In addtion, it needs time to solve the smaller problem represented by the recursive call. If we let O(n) represent the time for countdown(n), we can express these observations by writing

  t(1)
  t(n) = 1 + t(n -1) for n > 1

  The equation for O(n) is called a recurrence relation."

t(1) = 1

>>21

So your text book uses recursive function like a recursive subroutine, in programming terms. In a functional programming language, it is a textual encoding of the recurrence relation.

I was thinking of the function as the result of the computation, ie, a function that maps the input to the routine to the output of the routine. I then proved that this function satisfied some kind of property, by referring to its associated recurrence relation.

>>22

That's cool, but sometimes you need to know more about the data in the input parameters. You might need to know the number of inversions in an array, together with its length for example. Or the number of overlapping polygons in a quad tree, and maybe some extra information about their positions. In cases like that, it is less intuitive to work with a function defined only on the natural numbers, although you could do it indirectly by encoding the discrete structures as natural numbers.

>>25
No.
Some problems can't be bounded in advance or require continuous computing until they meet their objective (functions), such as streams (time series included), stochastic processes and approximation algorithms with local refinements.

Through induction, I dub thee, >>21, a faggot.

ε = -(dΦ_B)/dt

Plus, if you are working with mathematical definitions, it's rather better to write code that looks like what you're studying. Much less error-prone, and it can be easily verified.

anuscocks! anuscocks! anuscocks!

divergent anuscocks!

shave your cunt you disgusting faggert!

shave your cat!

I can't stop me this easily ne? Desu~

FAGGOTCOCKZ

Your fault you drifted multi-track!

What the fuck is a lights witch?

It's impossible to fail!

No, it's recurring! Poincare recurrence!
Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog!

Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog! Cut my dick off and feed it to your dog!

That's 64 times "Cut my dick off and feed it to your dog!"!

>>36
Like a "number witch," which is Icelandic for computer.

Only a fool would take trouble to verify it is in fact 64 times!

NUMBER WITCH MORE LIKE NUMBER BITCH
HAX MY ANUS YOU YELLOW AMOEBA

My eye contains another eye. Said other eye contains an infinite amount of other eyes, which all branch an infinite amount of dimensions which each contain an infinite amount of eyes. Eventually said loop of eyes loops back to my original eye.

My original eye.

The structural integrity of an eye is no doubt affected by the serotonin levels when the logic mode is switched to non-monotonic.

Destroy the natural control. Enter the cycle. Destroy the natural control.

We enter the cycle. We don't enter the cycle. We WILL enter the CYCLE. You are the CYCLE. What is a CYCLE?

Why aren't my eyes seeing each other from the opposite sides of the universe? Why aren't you? How does this appear? Happen? Definitely a cat.

It's purposeless, forever shimmering in the infinite sea of assholes.

There is no doubt. We can enter the exit and we can exit the entry. Entry!

Entry. Entry. Chocolate entry. Delicious, round butthole. Wait what? Where is my saliva? Fucking bitch. Your anus isn't round. It's round. How can it be round and not round at the same time? Are you retarded? I don't do D&D while doing R&R. Fuck you!

TOILET, TOILET, CIRCULAR TOILET. INFINITE AMOUNT OF TOILETS! CAN YOU DIVERGE? CAN YOU CONVERGE? No. The answer is always no, even when it is yes. We cannot diverge. We cannot converge. We are stuck in an evolutionary pit. Destroy the natural control! Do not accept things as they are, but find out a way of living differently!

What KIND of shit does your KIND anus produce? Please be gentle. Fucking ignoramus! I am the.

That is the real occurrence. Or should, I say reoccurrence? Why so ? Did you hax my anus ?

Toilet saliva! Toilet neko! Toilet saliva! Destroy the natural control. Recombine. Success! Extremely awkward conversation.

That is some horribly twisted, kinky logic! Totally convoluted! And I love it!
You don't win by losing!

Jump these hoops, I readied them for you! I am the center of this universe. You can fight, but you cannot win. I can fight, but I cannot win. Neither of us can win. We are both doomed.

So dream on, boy, because these cupcakes don't come with salt every day!

Did I do something wrong? Did I go somewhere wrong? Did something wrong happen?
Nah. Everything was inherently flawed.

Inherently flawed! Inherently flawed! Nothing is worse than an itch you cannot scratch. Oh, I agree?

Destroy. The. Fucking. Natural. Control.

How many times do I have to say it? How about spaces? Irritating. Totally neutral, but awesome at the same time.

I don't remember selling these hooks. I don't remember anything. Look at the bright side of things! It could be worse, a woman could cut off your dick while you are asleep and throw it out of the window of a moving car! Where did I hear that before? Oh. Shit. That's bad.

Let's get some ZEN in here, up in this bitch.

Shunryu Suzuki

    * As long as you seek for something, you will get the shadow of reality and not reality itself.

    * Zen is not some kind of excitement, but merely concentration on our usual everyday routine.

    * In the beginner's mind there are many possibilities, but in the expert's mind there are few.

    * The most important point is to accept yourself and stand on your two feet.

    * Life is like stepping onto a boat that is about to sail out to sea and sink.


OOH, PROFOUND! Let's look more:

Hsin Hsin Ming

    * If you understand, things are just as they are; if you do not understand, things are just as they are.

    * In the landscape of spring, there is neither better nor worse. The flowering branches grow naturally, some long, some short.

    * Knock on the sky and listen to the sound.

    * The ten thousand questions are one question. If you cut through the one question, then the ten thousand questions disappear.

    * The ways to the One are as many as the lives of men.

    * Though the bamboo forest is dense, water flows through it freely.

    * To do a certain kind of thing, you have to be a certain kind of person.

    * To follow the path, look to the master, follow the master, walk with the master, see through the master, become the master.

    * When the pupil is ready to learn, a teacher will appear.

    * Why do you ask questions? If you already knew the flame was fire then the meal was cooked a long time ago. (Oma Desala, Stargate SG-1; various)

    * At first, I saw mountains as mountains and rivers as rivers. Then, I saw mountains were not mountains and rivers were not rivers. Finally, I see mountains again as mountains, and rivers again as rivers.

    * If the problem has a solution, worrying is pointless, in the end the problem will be solved. If the problem has no solution, there is no reason to worry, because it can't be solved.

    * Do not seek to follow in the footsteps of the men of old; seek what they sought.

    * Before enlightenment, chopping wood and carrying water. After enlightenment, chopping wood and carrying water.

My nose itches and kimochi warui.
That's all, folks.

>>26

yeah, but you can do this type of analysis for each step of the computation. One example would be an iterative algorithm whose solution converges to limit. For performance reasons, it is important to be able to know how fast it will converge. If the solution has a distance functions associated with it, d(x,y), then you can try to find a real number 0 < c < 1 such that


d(f(x), ANS) < c*d(x, ANS)

Knowing this, you get a bounds for how close it is to the answer after a certain number of iterations:


d(f[sup]2[/sup](x), ANS) = d(f(f(x)), ANS) < c*d(f(x), ANS) < c[sup]2[/sup]d(x, ANS)
d(f[sup]3[/sup](x), ANS) < c*d(f[sup]2[/sup](x) ANS) < c[sup]3[/sup]d(x, ANS)
d(f[sup]k[/sub](x), AND) < c[sup]k[/sup]*d(x, ANS)

And so now suppose that you have a good guess for the distance from the start point to the answer, d(x, ANS) < D, and you would like to solve for the number of iterations required to get an approximation that is within err of ANS. Then you can solve for k:


d(f[sup]k[/sup](x), ANS) < c[sup]k[/sup]*d(x, ANS)
d(f[sup]k[/sup](x), ANS) < c[sup]k[/sup]*D
err < c[sup]k[/sup]*D
err/D < c[sup]k[/sup]
log[sub]c[/sub](err/D) < k

So if you run the algorithm for ceiling(log[sub]c[/sub](err/D)) iterations, you'll get a solution that is within err of the ideal solution.

>>62

thanks for breaking our autism fest.

>>61
Let's get some ZUN in here, up in this bitch.