Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Try doing a binary tree with tail recursion.


'Doing a binary tree'? You mean visiting every node?

  define walk-tree (tree fn &optional remaining-branches)
    match tree
      (Leaf l) ->
        funcall fn l
        if remaining-branches
          walk-tree (first remaining-branches) fn (rest remaining-branches)
      (Tree t r l) ->
        funcall fn t
        walk-tree r fn (push l remaining-branches)


It’s not as difficult as you might think; take the recursive code and turn it into CPS style.


A binary tree is a data structure, tail recursion is used in code ⇒ what algorithm are you thinking of that can be implemented in fixed space but is hard or impossible to do with tail recursion?


I’m not going to apologize for being harsh. But I will link a resource to help you understand. http://cslibrary.stanford.edu/110/BinaryTrees.html


This page does not identify an algorithm that can be implemented in fixed space but is hard or impossible to do with tail recursion. No such algorithm exists. It is unclear which of the dozens of beautiful algorithms it presents you mistakenly believed to be one.

tmtvl's comment at https://news.ycombinator.com/item?id=41983916 shows an algorithm that requires unbounded space.

Traversing a mutable binary tree can be done in fixed space but is not easier to do with generalized forms of recursion than with tail recursion or imperative iteration.


You should, because not only are you being rude you are also wrong.


By saying code is used to access a binary tree? lol


For saying that you cannot write algorithms to deal with binary trees using tail recursion. Saying code is used to access a binary tree is a trivial statement with no value to it. Nobody is going to even bother responding to that because of how obvious it is.


are you kidding me right now? How do you think the data structure is accessed? Hint: code

You youngun's have hidden behind APIs for so long you don't even know how things work.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: