6 ms·
> If you have a recursive data structure, using tail recursion over that structure is significantly more straightforward than writing iteratively. I actually wr
by kbp 7y ago
> 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 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 7y ago> 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?