> If you have a recursive data structure, using tail recursion over that structure is significantly more straightforward than writing iteratively. I actually wrote a comment about this recently: [0].
That example isn't tail recursive, though. The Python version is more difficult to read because you're using a manual stack instead of relying on the built-in one. An iterative algorithm, whether written using lexical recursion or a for loop, would entirely remove the use of a stack, not just hide the stack in your language implementation. Converting an iterative algorithm between the two forms is a simple syntax transformation, and doesn't introduce bookkeeping like that. Converting a body recursive function to iterate with an in-language stack introduces a lot of noise even if you use tail recursion to do the iteration.
The tail recursive Haskell version of your Python isn't much better:
sumTree :: BTree -> Int
sumTree t = sumTree' [t] 0
where sumTree' [] total =
total
sumTree' (Leaf v : rest) total =
sumTree' rest (v + total)
sumTree' (Branch v l r : rest) total =
sumTree' (l : r : rest) (v + total)
Oh damn, you're completely right. My mistake! I guess I should've actually re-read my comment before linking here since they were about slightly different things haha. Oh well.
> The Python version is more difficult to read because you're using a manual stack instead of relying on the built-in one.
For a sufficiently large input, Python will error due to its maximum stack recursion depth (default is 1000, I think), so a generic solution requires using an in-language stack or else modifying your Python configuration to circumvent the maximum. (Or using a different language, I suppose.)
> The tail recursive Haskell version of your Python isn't much better
I do find that less readable than the non-tail-recursive version I had written previously, but still easier to read than the Python version with an explicit stack.
An alternative approach might be to use a zipper instead of a list, but that's probably (definitely) over-engineering the problem haha.
Actually for fun I put together a zipper-y solution. It takes a lot of scaffolding, but if we assume the zipper stuff was already implemented then the `sumTree` solution itself is nice enough:
data BTree
= Leaf Int
| Branch Int BTree BTree
data Path
= Top
| InLeft Int Path BTree
| InRight BTree Int Path
type Location = (BTree, Path)
data Direction
= Up
| Down
goDownLeft :: Location -> Location
goDownLeft (Leaf _, _) = error "down of Leaf"
goDownLeft (Branch v l r, p) = (l, InLeft v p r)
goDownRight :: Location -> Location
goDownRight (Leaf _, _) = error "down of Leaf"
goDownRight (Branch v l r, p) = (r, InRight l v p)
goUp :: Location -> Location
goUp (_, Top) = error "up of Top"
goUp (l, InLeft v p r) = (Branch v l r, p)
goUp (r, InRight l v p) = (Branch v l r, p)
sumTree :: BTree -> Int
sumTree t = sumTree' Down (t, Top) 0
sumTree' :: Direction -> Location -> Int -> Int
sumTree' Down l r = case l of
(Leaf v, _) -> sumTree' Up l (v + r)
_ -> sumTree' Down (goDownLeft l) r
sumTree' Up l r = case l of
(_, Top) -> r
(_, InLeft{}) -> sumTree' Down (goDownRight (goUp l)) r
(_, InRight _ v _) -> sumTree' Up (goUp l) (v + r)
I feel like there's maybe a way to implement this more efficiently (like with a better choice of zipper constructors), but I really don't have a ton of experience with zippers so this is what I came up with. Maybe you know a better way?
> [0] https://news.ycombinator.com/item?id=20896327
That example isn't tail recursive, though. The Python version is more difficult to read because you're using a manual stack instead of relying on the built-in one. An iterative algorithm, whether written using lexical recursion or a for loop, would entirely remove the use of a stack, not just hide the stack in your language implementation. Converting an iterative algorithm between the two forms is a simple syntax transformation, and doesn't introduce bookkeeping like that. Converting a body recursive function to iterate with an in-language stack introduces a lot of noise even if you use tail recursion to do the iteration.
The tail recursive Haskell version of your Python isn't much better: