Recursion

#1 I would recommend looking at the wikipedia article on recursion in computer science for specific implementation methodologies anre reasons behind the usage. It is a much better explanation than I could probably give. Especially in terms of binary searches.

#2 I liked recursion when I was in college, one of the two things I was better at than even the teachers. Too bad my school's compsci department sucked so badly I decided it was better to just cut my losses and quit instead of continuing to pay $10k a year for dos programming in 2001.

And if wikipedia hasn't convinced you, I've got an example function that does a color fill just like the paint can tool in ms paint. It's simple but like all recursion it can be really confusing once it starts running.

#3 Anything you can do with recursion, could be done more efficiently with for loops (or any other type of loop).
If you're not concerned about performance, recursive functions may or may not make your life easier. But they're obviously slower than non-recursive ones.

#4 Ugh, I've rewritten this message too many times. Yay for indecisiveness.

Iteration is not always more efficient than recursion. Recursion's resource use all depends on the specific case and application. For example, a simple maze pathfinding function could be extremely lightweight and depending on the win path of the specific maze could find the correct exit without any dead paths.

They are not "obviously slower", iteration is not always more efficient.
Try a google search for iteration vs recursion.


Jeramy's example of a recursive function that's completely linear is a bad example. Pathfinding, area grouping, anything that requires possible branching, that's what recursion is for.

#5 I got the feeling that anything you code in imperative program languages, should be iterative if possible, and anything written in in functional programming languages that support lazy evaluation, should be written recursivly.

My teacher had a recursive add function for a binary search tree, and yet he got pissed when our splay tree that extended his BSP class employed a recursive get method.
p = root;

get(Node t, p)
{


if(t > p)
get(t, p.right);
elseif (t < p)
get(t, p.left);
else
return p;
}

His add method had pretty much the same structure.
Although he should, because it was pretty retarded, and it took only about 5 minutes to write it iterativly.

Edit:
Come to think about it, it is a while different story writing the add method recurisvly compared to the get method. First off, the add method returns a boolean or is simply a void method, and secondly...eer. Forgot the second reason.

#6 Recursive functions are "obviously slower" (but it seems it's not so obvious) because every time you do a function call you have to push the values of lots of register onto the stack and pop them later when the function is finished. Including the return address.

If you use a for loop, you don't have to do that. You save only the values of the registers you need, and you don't have the overhead of function calls.

The performance cost may not be obvious when you write your functions in c++, but that's what happens at a lower level anyway.

#7 Hadoken, the tone of your post is what set this off.

You used the qualifier "always", when infact, if you were to do a cursory search like I mentioned before, would find there are infact cases where recursion is not only simpler, but less resource intensive, no matter what the language you're using.

I'm going to use torque script here for the hell of it.
A simple recursive flood fill, with a couple obvious tweaks to streamline it a tiny bit. Like making the old and new color variables global since they don't change during a recursive instance.

Globals:
$imageMap
$oldColor
$newColor

function fillArea(%x, %y)
{
setColor($imageMap, %x, %y, $newColor);

if(getColor($imagemap, %x + 1, %y) == $oldColor)
fillArea(%x + 1, %y);
if(getColor($imagemap, %x, %y + 1) == $oldColor)
fillArea(%x, %y + 1);
if(getColor($imagemap, %x - 1, %y) == $oldColor)
fillArea(%x - 1, %y);
if(getColor($imagemap, %x, %y - 1) == $oldColor)
fillArea(%x, %y - 1);
}

Now, show me an iterative loop version of that, one that is faster against ALL cases, including a starting pixel that has no qualifying neighbors.


If you're going to use the word "always", be prepared to back it up, especially if you decide to imply that I'm just not quite understanding the underlying mechanisms of a program that your apparent superior intellect finds glaringly obvious.

#8 I don't understand why people are so touchy on this subject... I wasn't trying to offend you, I was just saying that recursive functions are slower, which is a fact. I think i know, having tested it many times. And I think it's obvious that a program doing fewer operations and using less memory is faster.

Now I have absolutely no interest in proving you wrong. Certainly I'm not going to learn all the details of torquescript just to do that.

However, if you're really interested in seeing whether recursive functions are slower or not (as opposed to proving me wrong because you didn't like the tone of my post), write a recursive c++ function that does that, and I'll write a non-recursive one that does the same thing. Then we'll test them with realistic cases, say 1024x768 images (let's use simply an array of pixels to make it easier), and see which one is faster.

The only purpose of this would be determining whether recursive functions are slower than iterative ones, it's not a competition for the fastest flood fill function ever, so there's no need to use fancy scan-line algorithms. If you can translate that thing you wrote into a simple c++ application that compiles, that would be enough.

#9 This is an interesting discussion.

Andrew, i did the search you recommend, and pretty much only find pages which say that recursion's claim to fame is that it simplifies code which can otherwise be thorny. However the only examples these pages seem to use are the simple ones of Fibonacci, not something more complex like flood fill.

In your flood fill case, if i was really concerned about performance,
i would perhaps "unroll" the recursion, so that the minimal amount of information goes on the stack.

Out of curiosity, do you consider something like the following to be recursive ?

function fillAreaDeRecursed(%x, %y)
{
   %stack = new Stack();
   
   %stack.push(%x);
   %stack.push(%y);
   
   while (%stack.isNotEmpty())
   {
      %y = %stack.pop();
      %x = %stack.pop();
      
      setColor($imageMap, %x, %y, $newColor);

      testAndPush(%stack, %x + 1, %y    );
      testAndPush(%stack, %x - 1, %y    );
      testAndPush(%stack, %x   1, %y + 1);
      testAndPush(%stack, %x   1, %y - 1);
   }
   
   %stack.delete();
}

function testAndPush(%stack, %x, %y)
{
   if (getColor($imagemap, %x, %y) == $oldColor)
   {
      %stack.push(%x);
      %stack.push(%y);
   }
}

#10 I would consider that to be the iterative version of the function that was posted above. I would consider recursive only those functions that call themselves.

The reason why i suggested doing it in c++, is that it's certainly possible to internally implement loops in a way that they're as inefficient as recursion, which could be the case in torquescript as far as i know, because i know nothing about the torquescript compiler.

But if the compiler does its job properly (which is usually the case with the MS c++ compiler), I think there's no way a recursive function could be faster than its iterative counterpart.

#11 It's funny. Technically it's not recursion, but it is using the exact same datastructures and using the exact same operations on them. After thinking about it a bit, i would like to say that my code and Andrew's are in fact identical algorithms, just one version puts less stuff on the stack.

Re C++ vs Torquescript, i think any functional language should be sufficient to have this sort of discussion.

#12 Hadoken: It got touchy when you made your post alluding that I just wasn't understanding the glaringly obvious efficiency issues, and then went one to explain the very basics of function calls.
If you hadn't tossed recursion aside as "always less effecient", keyword always, I wouldn't have bothered. But the tone of your posts have all been that recursion is just not worth it. Very unhelpful in a thread started by someone who doesn't yet understand what recursion is.

Also, single pixel fill test cases are quite valid. Artists of all ages using programs like MS Paint tend to use it for 1 and 2 pixel fills just to save the time of swapping back and forth with the pen tool.


Orion: You're right, your example handles the data exactly like mine.
Heck, putting them side by side with some real usage data on test cases would be the perfect example of iterative vs recursion.

#13 Now you've brought up stacks, I seem to remember a bunch of stuff about how a stack is more easily represented using a recursive data structure, while a queue is more easily represented through an iterative one. But I may be imagining things.

Quote:Out of curiosity, do you consider something like the following to be recursive ?

Kindasortanotreally. I consider it a really hideous way to implement a recursive algorithm using your own stack instead of the language's callstack. Technically I don't consider it recursive since the function never calls itself.

Something else that's worth noting is that any compiler worth its salt [including GCC, llvm, visual C&friends] recognises a tail recursive algorithm when it sees one, and will completely optimise out the stack. Hadoken's main argument appears to be that stack management overhead is a greater cost than iterative loop overhead, but stack management is actually free [or close to it] in the case of tail recursion.

Gary (-;

#14 Yes, that's what i meant. Using explicit recursion is like telling the compiler to do the stack management for you. But the compiler doesn't know which values you really need, so it saves some extra stuff that you could avoid if you used a loop.

True, the compiler could optimize it a bit in some cases, and could do what you would do manually. Usually though, my compiler is not that smart.
Running the flood fill example above (a c++ version compiled with visual studio), the program causes stack overflow even with a large stack size, which makes me think the compiler isn't optimizing the recursion away.

About the flood fill example above, there's actually a difference in the order in which the pixels are processed, which i think is interesting, although in the end it makes no difference.

@Andrew: apologies, like i said, no offense intended