Recursion, Part One: Recursive Data Structures and Functionshttp://blogs.msdn.com/b/ericlippert/archive/2005/07/27/recursion-part-one-recursive-data-structures-and-functions.aspxThe first thing to wrap your head around is recursively defined data structures. Let's start with something simple. Think about the abstract idea of “list”. Most people think of a “list” as an ordered collection of “items”, one after the other, with aen-USTelligent Evolution Platform Developer Build (Build: 5.6.50428.7875)re: Recursion, Part One: Recursive Data Structures and Functionshttp://blogs.msdn.com/b/ericlippert/archive/2005/07/27/recursion-part-one-recursive-data-structures-and-functions.aspx#8793292Thu, 31 Jul 2008 16:09:20 GMT91d46819-8472-40ad-a661-2c78acb4018c:8793292Pierre<p>Yip Simon you're right about the binary search tree part, the rest is sweet.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=8793292" width="1" height="1">re: Recursion, Part One: Recursive Data Structures and Functionshttp://blogs.msdn.com/b/ericlippert/archive/2005/07/27/recursion-part-one-recursive-data-structures-and-functions.aspx#700606Tue, 15 Aug 2006 06:57:32 GMT91d46819-8472-40ad-a661-2c78acb4018c:700606SimonIt'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.
<br><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=700606" width="1" height="1">Recursionhttp://blogs.msdn.com/b/ericlippert/archive/2005/07/27/recursion-part-one-recursive-data-structures-and-functions.aspx#453289Fri, 19 Aug 2005 01:27:33 GMT91d46819-8472-40ad-a661-2c78acb4018c:453289Peter Stathakos - Stack Of Toast<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=453289" width="1" height="1">re: Recursion, Part One: Recursive Data Structures and Functionshttp://blogs.msdn.com/b/ericlippert/archive/2005/07/27/recursion-part-one-recursive-data-structures-and-functions.aspx#448122Fri, 05 Aug 2005 18:42:57 GMT91d46819-8472-40ad-a661-2c78acb4018c:448122David Walker"Most people think of a “list” as an ordered collection of “items”,..."
<br>
<br>I like lists where any item can itself be a list. And so on. Nested lists.
<br>
<br>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.<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=448122" width="1" height="1">Eric Lippert on Recursionhttp://blogs.msdn.com/b/ericlippert/archive/2005/07/27/recursion-part-one-recursive-data-structures-and-functions.aspx#444773Fri, 29 Jul 2005 07:41:10 GMT91d46819-8472-40ad-a661-2c78acb4018c:444773notgartner.com: Mitch Denny's Blog<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=444773" width="1" height="1">re: Recursion, Part One: Recursive Data Structures and Functionshttp://blogs.msdn.com/b/ericlippert/archive/2005/07/27/recursion-part-one-recursive-data-structures-and-functions.aspx#444713Fri, 29 Jul 2005 04:01:35 GMT91d46819-8472-40ad-a661-2c78acb4018c:444713Muhammad Ali ShahRecursion 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.
<br>
<br>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.<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=444713" width="1" height="1">re: Recursion, Part One: Recursive Data Structures and Functionshttp://blogs.msdn.com/b/ericlippert/archive/2005/07/27/recursion-part-one-recursive-data-structures-and-functions.aspx#443848Wed, 27 Jul 2005 18:29:59 GMT91d46819-8472-40ad-a661-2c78acb4018c:443848esteeOh, Eric, what a good article!
<br>
<br>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:
<br>
<br>['html',{lang:'en-US'}
<br> ['head',
<br> ['title']
<br> ['meta',{name:"Generator",content:"Microsoft Visual Studio .NET 7.1"}],
<br> ['meta',{name:"vs_targetSchema",content:"<a rel="nofollow" target="_new" href="http://schemas.microsoft.com/intellisense/ie5"">http://schemas.microsoft.com/intellisense/ie5"</a>}]
<br> ],
<br> ['body','<!--insert your HTML here-->']
<br>]
<br>
<br>(Recursive JS code to generate text out of this tree is trivial, of course. Follow the link above to see my impl.)
<br>
<br>(Sorry, I'm not so smart to generalise this example to something more interesting, like C# trees.. i'm just recursion consumer ;-)<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=443848" width="1" height="1">re: Recursion, Part One: Recursive Data Structures and Functionshttp://blogs.msdn.com/b/ericlippert/archive/2005/07/27/recursion-part-one-recursive-data-structures-and-functions.aspx#443805Wed, 27 Jul 2005 16:20:24 GMT91d46819-8472-40ad-a661-2c78acb4018c:443805Svend TofteThis 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.
<br>
<br>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.
<br>
<br>You just need to look at it, until the dime drops. This of course also explains why programmars count 0, 1, many ;-)<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=443805" width="1" height="1">