[Python-Dev] Proper tail recursion (original) (raw)
Andrew Koenig ark-mlist at att.net
Thu Jul 15 18:07:53 CEST 2004
- Previous message: [Python-Dev] Prototypes [was: Proper tail recursion]
- Next message: [Python-Dev] Proper tail recursion
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
But in this case what is tail-call optimization going to do for you? You still require a stack at least the size of the height of your tree because of traverse(t.left) since that can not be tail-call optimized away, with the proposed algorithm.
I thought I had pointed that out. Lisp lists are really trees, the nodes of which usually have very short left subtrees. For example, (3 (4 5) 6 7 8) is a tree in which the maximum left depth is 2 and maximum right depth is 5. For such data structures, tail-call optimization would make a big difference in practice even if it wouldn't matter in theory.
- Previous message: [Python-Dev] Prototypes [was: Proper tail recursion]
- Next message: [Python-Dev] Proper tail recursion
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]