Recursion

  • (2 Pages)
  • +
  • 1
  • 2

24 Replies - 3545 Views - Last Post: 02 August 2008 - 05:38 PM

Poll: Recursion (27 member(s) have cast votes)

Recursion is awesome (?)

  1. Yes (21 votes [77.78%])

    Percentage of vote: 77.78%

  2. No (6 votes [22.22%])

    Percentage of vote: 22.22%

Vote Guests cannot vote

#1 Tom9729  Icon User is offline

  • Segmentation fault
  • member icon

Reputation: 180
  • View blog
  • Posts: 2,641
  • Joined: 30-December 07

Recursion

Posted 29 July 2008 - 07:17 AM

Just thought I'd give a shout out to recursive functions, which are making me dizzy but are really cool nevertheless. :D
Is This A Good Question/Topic? 0
  • +

Replies To: Recursion

#2 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5931
  • View blog
  • Posts: 12,853
  • Joined: 16-October 07

Re: Recursion

Posted 29 July 2008 - 08:30 AM

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.
Was This Post Helpful? 0
  • +
  • -

#3 Tom9729  Icon User is offline

  • Segmentation fault
  • member icon

Reputation: 180
  • View blog
  • Posts: 2,641
  • Joined: 30-December 07

Re: Recursion

Posted 29 July 2008 - 10:52 AM

View Postbaavgai, 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

Was This Post Helpful? 0
  • +
  • -

#4 Moonbat  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 36
  • View blog
  • Posts: 424
  • Joined: 30-June 08

Re: Recursion

Posted 29 July 2008 - 07:01 PM

I really like recursion. I used it for a factorial function in PHP a few days ago; it's very useful.
Was This Post Helpful? 0
  • +
  • -

#5 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2271
  • View blog
  • Posts: 9,499
  • Joined: 29-May 08

Re: Recursion

Posted 29 July 2008 - 07:28 PM

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

Was This Post Helpful? 0
  • +
  • -

#6 Tom9729  Icon User is offline

  • Segmentation fault
  • member icon

Reputation: 180
  • View blog
  • Posts: 2,641
  • Joined: 30-December 07

Re: Recursion

Posted 29 July 2008 - 07:41 PM

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

Was This Post Helpful? 0
  • +
  • -

#7 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2271
  • View blog
  • Posts: 9,499
  • Joined: 29-May 08

Re: Recursion

Posted 29 July 2008 - 07:41 PM

At last a use for :basecase:
Was This Post Helpful? 0
  • +
  • -

#8 Tom9729  Icon User is offline

  • Segmentation fault
  • member icon

Reputation: 180
  • View blog
  • Posts: 2,641
  • Joined: 30-December 07

Re: Recursion

Posted 29 July 2008 - 08:04 PM

A recursive smiley face, oh heavens.
Was This Post Helpful? 0
  • +
  • -

#9 Programmist  Icon User is offline

  • CTO
  • member icon

Reputation: 252
  • View blog
  • Posts: 1,833
  • Joined: 02-January 06

Re: Recursion

Posted 30 July 2008 - 05:03 AM

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.
Was This Post Helpful? 0
  • +
  • -

#10 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Recursion

Posted 30 July 2008 - 05:31 AM

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.)
Was This Post Helpful? 0
  • +
  • -

#11 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2271
  • View blog
  • Posts: 9,499
  • Joined: 29-May 08

Re: Recursion

Posted 30 July 2008 - 12:28 PM

View PostAdamSpeight2008, 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

Was This Post Helpful? 0
  • +
  • -

#12 Einherjar  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 73
  • Joined: 10-February 08

Re: Recursion

Posted 30 July 2008 - 01:25 PM

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 ;)
Was This Post Helpful? 0
  • +
  • -

#13 Programmist  Icon User is offline

  • CTO
  • member icon

Reputation: 252
  • View blog
  • Posts: 1,833
  • Joined: 02-January 06

Re: Recursion

Posted 31 July 2008 - 06:06 AM

View PostNickDMax, 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.
Was This Post Helpful? 0
  • +
  • -

#14 OliveOyl3471  Icon User is offline

  • Everybody's crazy but me!
  • member icon

Reputation: 134
  • View blog
  • Posts: 6,581
  • Joined: 11-July 07

Re: Recursion

Posted 01 August 2008 - 12:33 AM

View PostTom9729, 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. :sarcasm: :D
Lisp? You sure that's not spelled Lithp?
lol ;)
Was This Post Helpful? 0
  • +
  • -

#15 RodgerB  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 66
  • View blog
  • Posts: 2,284
  • Joined: 21-September 07

Re: Recursion

Posted 01 August 2008 - 04:20 AM

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.
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2