Self function

[Steven D'Aprano]

On Mon, 04 May 2009 23:55:41 -0700, Carl Banks wrote:

> On May 4, 8:26 pm, Steven D'Aprano
> <ste... at REMOVE.THIS.cybersource.com.au> wrote:
>> 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".
> 
> No, many implemenations of singly-linked lists aren't trees by any
> definition.

I would say not. Nodes with a single link field can't form a tree, 
because you can't give it a left and right child. However trees can 
degenerate into a singly-linked list, where each node has at least one 
unused child. That is what both Bearophile and I are trying to tell you. 
It's not that anyone sane thinks "I know, I'll use a binary tree to 
implement a linked list" -- that would be stupid, and shame on you for 
thinking that Bearophile is that stupid. But if you insert data into a 
non-self-balancing tree, sometimes the tree will degenerate into a linked 
list with extra, unused child links.


[...]
> But even singly-linked lists implemented with cons cells can be handled,
> and are better handled, with interation.

Can be, certainly.

Better? Maybe.


>> >> >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.
> 
> Then it't not a singly-linked list.  It's a tree.

It was already a tree. It's just that the entire tree happened to form 
one long chain.



>> What
>> are you suggesting, that Bearophile should write his tree-processing
>> code to only deal with the degenerate case?
> 
> I'm suggesting that Bearophile should write recursive code for his trees
> and iterative code for his lists.

But his tree-handling recursive code MUST and WILL operate on degenerate 
trees that form chains (linked lists), unless he writes more complicated 
code to avoid it (e.g. red-black trees). For simple trees, you don't have 
the luxury of saying "Oh, my trees will never be degenerate, they'll 
always be optimal, with the minimum depth possible." You get the trees 
you're given, and sometimes they'll be one long branch with no, or very 
fewer, off-shoots, and you'll have O(N) performance instead of O(log N).

And the clever thing?

Just write the recursive code, as normal, and it will magically handle 
the degenerate case too.



>> >> 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.
> 
> If you have a tree, then you use recursive code.  If you have a list you
> use iterative code.

I wish to retract my poorly worded comment "And a linked list is a 
degenerate tree". That is incorrect. What I should have said is that a 
degenerate tree behaves equivalently to a linked list, rather than "is".



>> > 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.
> 
> Yeah, well, see that's just the point here.  Bearophile was asked if any
> of his trees go 1000 deep, he said yes, his singly-linked lists do. 

He certainly did not say anything of the sort.


> Well, I'm sorry, that's not going to convince me, because bearophile
> should be using iteration for the singly-linked lists.

What Bearophile actually wrote was:

"You are thinking just about complete binary trees. But consider that a 
topology LIKE a single linked list (every node has 1 child, and they are 
chained) is a true binary tree still." [Emphasis added.]

It should be obvious what he means. But if, by some chance, you 
misunderstood what he said, he replied to your earlier post and explained 
further:

"I was talking about a binary tree with list-like topology, of course."

If you don't understand what a binary-tree with a list-like topology is, 
then I respectfully suggest that you are unqualified to have an opinion 
in this discussion and you should come back when you've learned what a 
binary-tree with a list-like topology actually is, and why your 
suggestion that he use iteration on linked lists is, to quote Wolfgang 
Pauli, Not Even Wrong.


> Bearophile might very well have real trees that are 1000 deep, but
> that's not going to convince me either, because IMO real trees rarely do
> that, and Python's recursion limit can be increased in the rare cases
> they do.

Are you saying that Bearophile's trees are imaginary? That's he's making 
them up?

Personally, I don't think it's good to have a function fail just because 
it has to recurse over a mere 1000 items. I think that's as poor as some 
hypothetical language where you can't iterate over more than 1000 items, 
and if you try, you have to catch the exception, increase the iteration 
limit, and try again. People wouldn't stand for it.

Oh, I understand *why* Python has that limitation. It's just a black mark 
on an otherwise wonderful language.


[...]
>> > 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.
> 
> If one of the fields is always empty, you don't need recursion to deal
> with it.

That's just silly. How do you know that one of the fields is always empty 
until you've walked the tree?



[...]
> I'm not talking about degenerate trees.  I'm talking about singly-
> linked lists, which you DO NOT NEED, and SHOULD NOT USE, recursion to
> deal with.

Ah, then you are the one introducing the straw man, because Bearophile is 
talking about trees.



-- 
Steven