[kbp]

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

> [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:

  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)

[DonaldPShimoda]

> That example isn't tail recursive, though.

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?