Self function

[Carl Banks]

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.  You are probably thinking of the bastardized list-tree
spawn they use in Lisp.  But many implementations don't even bother
with a cons cell and just have the object itself refer to the next
object.  That is not a tree.

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


> >> >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.


> 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.


> >> 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.


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

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.

Bearophile and you are welcome to try to convince me that there are
lots of real trees out there that can't be handled with iteration and
that do go 1000 deep, and that this is a common enough problem that
Python should drastically improve support for recursion.  Until then I
will opine that it is adequate now for almost all purposes.


> > 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.


> > [snip strawman example]
>
> It's not a strawman just because you don't like it.

No, it's a strawman because I said singly-linked lists don't need
recursion, and his counterexample was showing that recursion was
useful a tree.  Which was true, but it wasn't answering my argument.


> 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.

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.


Carl Banks