18 ms·
Try doing a binary tree with tail recursion.
by CodeWriter23 2y ago
Try doing a binary tree with tail recursion.
- deleted 2y ago[deleted]
- tylerhou 2y agoIt’s not as difficult as you might think; take the recursive code and turn it into CPS style.
- Someone 2y agoA 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?
- CodeWriter23 2y agoare 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.
- CodeWriter23 2y agoI’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 http://cslibrary.stanford.edu/110/BinaryTrees.html
- kragen 2y agoThis 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 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.
- saagarjha 2y agoYou should, because not only are you being rude you are also wrong.
- CodeWriter23 2y agoBy saying code is used to access a binary tree? lol
- saagarjha 2y agoFor 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.
- tmtvl 2y ago'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)