Self function

[Steven D'Aprano]

On Mon, 04 May 2009 16:33:13 -0700, Carl Banks wrote:

> On May 4, 4:06 pm, bearophileH... at lycos.com wrote:
>> Carl Banks:
>>
>> >1. Singly-linked lists can and should be handled with iteration.<
>>
>> I was talking about a binary tree with list-like topology, of course.
> 
> "(every node has 1 child, and they are chained)"
> 
> That's a singly-linked list, not a tree.  It's a degenerate tree at
> best.

A singly-linked list is a degenerate tree. Not "at best", but "is".


>> >All recursion does it make what you're doing a lot less readable for
>> >almost all programmers.<
>>
>> I can't agree.
> 
> If every child has one node you don't need recursion.

And if one single node in the entire tree has two children, you do. What 
are you suggesting, that Bearophile should write his tree-processing code 
to only deal with the degenerate case?



>> If the data structure is recursive (like a tree, or even sometimes
>> graphs, etc) a recursive algorithm is shorter, more readable and more
>> natural.
> 
> Because that's a tree, not a linked-list.

And a linked list is a degenerate tree. If you have a non-self-balancing 
tree, sometimes it will be degenerate, and your code needs to deal with 
it.


> Which is germane because Python's recursion limit is the thing you're
> complaining about here, and you don't normally hit that limit with real
> trees because they rarely go 1000 deep.

And if just ONE branch of the tree goes 1000 deep, even if the rest of 
the tree is shallow, then you hit the default recursion limit.


> Singly-linked lists don't count because you don't need recursion for
> them.

If each node has two (or more) child fields, even if only one of those 
children is non-empty, then your data structure is a degenerate tree and 
does count.



> [snip strawman example]

It's not a strawman just because you don't like it. Dealing with 
degenerate trees is a genuine issue, and avoiding degenerate trees is the 
reason why people have developed more complicated structures like red-
black trees.



-- 
Steven