[REBOL] Re: Tail end recursion
From: gedb01:yaho:o at: 9-Oct-2003 14:29
You probably know that recursion is when a function
calls itself. With tail end recursion LISP ensures
that recursion is as efficient as iteration [1].
Instead of iteration:
repeat count 3 [
print ["count: " count]
]
You would use:
recursive: func [count target][
print ["recursive count: " count]
if count < target [recursive count + 1 target]
]
recursive 1 3
In this simple example iteration looks much better.
The recursive approach looks complicated and difficult
to understand. So why is tail end recursion
desirable?
Well, consider a alogrithm for Longest Common
Subsequence [2]. As link 2 shows, the initial
recursive form is very easy to derive and understand,
but you have to work a lot harder to get a decent
iterative solution.
[1]
http://mathcs.holycross.edu/~mule/labs/prelabs/RecursionLambdaLab.htm
[2] http://www.ics.uci.edu/~eppstein/161/960229.html
