[Tom9729]

Just thought I'd give a shout out to recursive functions, which are making me dizzy but are really cool nevertheless.

[baavgai]

On the fence, voted no ( currently only one out of five to do so ).

Recursion is very clever. It can do vary particular things in an elegant way. It can functionally create a limited dynamic array by using the stack in an out side the box kind of way. I've used it for a number of cases where it was the cleanest, shortest path to the answer, but...

Recursion also seems to propagate the kind of mystical non intuitive snippets that C programmers take such joy in. In one sense, it's hard to truly grasp whats initially going on. Then, when the beginner inevitably gets there stack overflow, that answer to why it happened can be even less clear.

Recursion makes for very clean implementation of very complex algorithms, particularly the divide and conquer stuff. However, I suspect it is generally offered too soon in a curriculum to do the beginner any favors. Also, in the end, it is kind of a hack.

[Tom9729]

baavgai, on 29 Jul, 2008 - 11:30 AM, said:

Recursion also seems to propagate the kind of mystical non intuitive snippets that C programmers take such joy in. In one sense, it's hard to truly grasp whats initially going on. Then, when the beginner inevitably gets there stack overflow, that answer to why it happened can be even less clear.

That's true, but I think for something like crawling a tree of nodes the alternatives are worse.

I never learned about recursion in any of my computer science classes. I actually picked it up while reading a book on Lisp.

It's really too bad they don't teach Lisp anywhere I've heard of. It's a pretty nice language that really doesn't seem to get a lot of attention anymore.

Edit: Here's a recursive function from the PHP program I'm working on, for anyone curious/bored.

/**
 * Flatten a tree of nodes into a one-dimensional array.
 *
 * @param ctree A TreeNode.
 * @return A 1d array of alternating string/boolean.
 * @author Tom Arnold
 */
function tree_flatten($ctree)
{
  $items = array($ctree->title, $ctree->value);

  for ($i = 0; $i < sizeof($ctree->children); ++$i)
  {
    $more = tree_flatten($ctree->children[$i]);

    for ($j = 0; $j < sizeof($more); ++$j)
    {
      array_push($items, $more[$j]);
    }
  }

  return $items;
}

This post has been edited by Tom9729: 29 July 2008 - 10:54 AM

[Moonbat]

I really like recursion. I used it for a factorial function in PHP a few days ago; it's very useful.

[AdamSpeight2008]

How this for a cool recursion function (Pseudo code style), came up with it in 2004
Radix Sorting of 32 Bit Integers

List[] = FN_BinBinSort( List[], 32 )
END
:
DEF FN_BinBinSort( InList[], Depth )
IF Depth<0 THEN =InList[]
LOCAL DIM ListArray[1]{}
LOCAL i,
FOR i=1 TO InList[].Items
b = ( InList[]{i} AND ( &1 << Depth ) >> Depth )
ListArray[b].AddItem InList[]{i}
NEXT i
IF ListArray[0].Items>1 THEN ListArray[]=FN_BinBinSort( ListArray[0], (Depth-1) )
IF ListArray[1].Items>1 THEN ListArray[]=FN_BinBinSort( ListArray[1], (Depth-1) )
RETURN ListArray[0]+ListArray[1]
END FN

Is there any cooler?

This post has been edited by AdamSpeight2008: 29 July 2008 - 07:29 PM

[Tom9729]

The one thing I don't like about recursion is that it's a major brain-ache reading code that does it that you didn't write.

This post has been edited by Tom9729: 29 July 2008 - 07:41 PM

[AdamSpeight2008]

At last a use for

[Tom9729]

A recursive smiley face, oh heavens.

[Programmist]

A poll about how awesome recursion is. Seems kind of random. Why not have a poll about how cool derivatives are? Nevertheless, I'll weigh in and say that, while recursion does solve many problems cleanly and often is easily translated from a proof by induction, it is not as efficient as one would hope on today's typical architectures and should be used sparingly. First, space is a factor as the stack must store state at each recursive function call. Second, speed (time) is a factor. A function call is almost always more expensive that a jump (used in iteration) as it requires allocating and later releasing local memory, copying parameter values into local memory, and branching and returning. Elegance and conciseness are nice to have, but they are usually never as important as efficiency and readability.

[NickDMax]

However the recursive divide and conquer algorithms tend to lend themselves to the creation of concurrent algorithms. With Intel working on packing as many cores onto a die as they can cram in, it would seem that the future of computing is going to require more and more work in concurrency.

I voted for awesome. (course that may just be because I have been working in concurrent programming recently.)

[AdamSpeight2008]

AdamSpeight2008, on 30 Jul, 2008 - 03:28 AM, said:

How this for a cool recursion function (Pseudo code style), came up with it in 2004
Radix Sorting of 32 Bit Integers

List[] = FN_BinBinSort( List[], 32 )
END
:
DEF FN_BinBinSort( InList[], Depth )
IF Depth<0 THEN =InList[]
LOCAL DIM ListArray[1]{}
LOCAL i,
FOR i=1 TO InList[].Items
b = ( InList[]{i} AND ( &1 << Depth ) >> Depth )
ListArray[b].AddItem InList[]{i}
NEXT i
IF ListArray[0].Items>1 THEN ListArray[]=FN_BinBinSort( ListArray[0], (Depth-1) )
IF ListArray[1].Items>1 THEN ListArray[]=FN_BinBinSort( ListArray[1], (Depth-1) )
RETURN ListArray[0]+ListArray[1]
END FN

See snippet for a VB.Net Implementation.
Recursive Radix Sort (VB.Net Snippet)

This post has been edited by AdamSpeight2008: 30 July 2008 - 12:29 PM

[Einherjar]

I wasn't sure what to vote because I can see the use of recursion, but I try to use it sparingly as Programmist pointed out. Basically I don't use recursion just for recursions sake, but for the increase in efficiency or speed compared to the alternatives. So if you could make that bold part an answer, it would be perfect

[Programmist]

NickDMax, on 30 Jul, 2008 - 05:31 AM, said:

However the recursive divide and conquer algorithms tend to lend themselves to the creation of concurrent algorithms. With Intel working on packing as many cores onto a die as they can cram in, it would seem that the future of computing is going to require more and more work in concurrency.

I voted for awesome. (course that may just be because I have been working in concurrent programming recently.)

True. This is what I meant when I said it solves some problems cleanly. I'd be interested to hear any data on the increase in speed, on a multicore/SMP machine, from a regular merge sort to one that spins off a new threads on a split.

[OliveOyl3471]

Tom9729, on 29 Jul, 2008 - 12:52 PM, said:

I never learned about recursion in any of my computer science classes. I actually picked it up while reading a book on Lisp.

/**
 * Flatten a tree of nodes into a one-dimensional array.
 *
 * @param ctree A TreeNode.
 * @return A 1d array of alternating string/boolean.
 * @author Tom Arnold

I never learned recursion either, so I didn't vote in your poll. But since I don't want to be left out I will learn about it (sometime).

So you're Tom Arnold, eh? How's Roseanne?
Bet you never heard that before.
Lisp? You sure that's not spelled Lithp?
lol

[RodgerB]

I hate recursion for every reason presented on the hater fence. a) Every time I tried to do it in C# or VB.NET it would give me a stack overflow, b ) It's messy (do you call frizzy red heads elegant?) and c) iterations are easier for my mind to comprehend.