Snippets tagged tail recursion

  • sum the nodes in a (not-binary) tree using continuations

    you can easily find how to use continuations to iterate over a binary tree but what if the count of children for each node is not known at design time? It's not so obvious how to do this in order to get a tail-recursive method. This short snippet shows how to do this to sum the values of every leaf. The second part demonstrates a general approach for other operations than addition.

    26 people like this

    Posted: 13 years ago by Carsten König

  • Factorial

    Factorial versus tail recursion

    4 people like this

    Posted: 11 years ago by Laco

  • Rotate or shift lists

    This rotates or shifts a list. Unlike http://www.fssnip.net/qY/title/Rotate-List, which runs exponentially, this runs at O(n). In case of overflow (i.e., shift index is larger than the size of the list) will run at most once more with the modulo. This is done to prevent using `List.length` prior to entering the function, as that would lead to a perf punishment of an extra O(n) on each invocation. For large lists, `shift largeList 1` would then get a big performance hit.

    1 people like this

    Posted: 2 years ago by Abel Braaksma