Recursion, Part One: Recursive Data Structures and Functions

re: Recursion, Part One: Recursive Data Structures and Functions

Svend Tofte — Wed, 27 Jul 2005 16:20:24 GMT

This all takes me back to the first time I wrote any code at all. I needed a piece of code, that would iterate the DOM tree of NS4. I asked a CS guy nearby on my floor, and he gave me the recursive method. Wonderful stuff.

Recursion in and of itself, is not too hard. But when you start writing really hairy recursive stuff, that start folding out, and then folds back into itself, I once heard someone describe recursion as a koan.

You just need to look at it, until the dime drops. This of course also explains why programmars count 0, 1, many ;-)

re: Recursion, Part One: Recursive Data Structures and Functions

estee — Wed, 27 Jul 2005 18:29:59 GMT

Oh, Eric, what a good article!

By the way, yet another example of tree-like structures and their recursive processing comes to mind. This is (HT|X)ML dynamic generation. Once i saw how Perl deals with this, combining arrays and associative arrays to represent HTML tags/attrs, i often use it's JS equivalent. For instance, a simple HTML template might look like this in JS:

['html',{lang:'en-US'}
['head',
['title']
['meta',{name:"Generator",content:"Microsoft Visual Studio .NET 7.1"}],
['meta',{name:"vs_targetSchema",content:"http://schemas.microsoft.com/intellisense/ie5"}]
],
['body','']
]

(Recursive JS code to generate text out of this tree is trivial, of course. Follow the link above to see my impl.)

(Sorry, I'm not so smart to generalise this example to something more interesting, like C# trees.. i'm just recursion consumer ;-)

re: Recursion, Part One: Recursive Data Structures and Functions

Muhammad Ali Shah — Fri, 29 Jul 2005 04:01:35 GMT

Recursion is beautiful and perhaps, contrary to commonly held belief, it's many times more natural than iterative solutions which do not exploit the recursive nature of data structures or the problem at hand.

When they taught it for the first time in school, I thought, "What the heck? I can do this with a loop." But as we moved onto tree structures and more complex problems like the famous N-Queen problem, I knew that I loved it. Recursion truly stands out.

Eric Lippert on Recursion

notgartner.com: Mitch Denny's Blog — Fri, 29 Jul 2005 07:41:10 GMT

re: Recursion, Part One: Recursive Data Structures and Functions

David Walker — Fri, 05 Aug 2005 18:42:57 GMT

"Most people think of a “list” as an ordered collection of “items”,..."

I like lists where any item can itself be a list. And so on. Nested lists.

APL's "generalized arrays" work that way where any item of an array can be an array. Way back when, arrays were limited to 63 dimensions though.

Recursion

Peter Stathakos - Stack Of Toast — Fri, 19 Aug 2005 01:27:33 GMT

re: Recursion, Part One: Recursive Data Structures and Functions

Simon — Tue, 15 Aug 2006 06:57:32 GMT

It's a nice article. But the property that every parent is in between it's children isnt really significant for binary search trees. the important property is that every node left from the root is less than the root and every node right from it is more than a root..and again every node can itself be a root to a subtree.

re: Recursion, Part One: Recursive Data Structures and Functions

Pierre — Thu, 31 Jul 2008 16:09:20 GMT

Yip Simon you're right about the binary search tree part, the rest is sweet.