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.