I don't believe Tim's comments are correct. Since there are three recursive calls, I don't think there is a straightforward transformation to tail position using an accumulator. Also, due to the interleaved nature of the recursive calls, I would expect memoization to be essential.
So, I think the CPS transformation is in fact what is needed to make this top-down recursive implementation execute without blowing the stack. I looked at Christian's code briefly, and it looks to me that the CPS transformation was well done. Aside from a couple minor stylistic things (e.g., I think most would use [arg1 arg2] rather than (list arg1 arg2)), I don't see any obvious improvements to be made. If anyone sees a better way to make this particular approach work, I'd also be interested in seeing it. Of course, in most languages the Levenshtein distance is computed using the bottom-up Dynamic Programming strategy of filling in a matrix left-to-right, one row at a time, thus ensuring that all the entries needed to compute a given entry are already available. There is pseudocode for this approach on the Wikipedia, and I think I've seen both a Perl and Scheme solution that improve upon that by storing only one row's worth of data, rather than the full matrix. Clojure certainly would support such a strategy, and in fact, that's probably the better way to solve this problem. One way to implement the DP solution would be to pass the grid in an accumulator, and for such a strategy you wouldn't need memoization, so perhaps that's what Tim had in mind. But even though DP would be effective here, DP does not work for all recursive problems, and therefore, Christian's original question about how best to get the *recursive formulation* of this algorithm to run under Clojure using a methodical transformation is a valid one. -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
