On May 4, 8:26 pm, Steven D'Aprano <ste...@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...@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 -- http://mail.python.org/mailman/listinfo/python-list
