[plt-scheme] Recursion to iteration

From: Andrei Estioco (chadestioco at gmail.com)
Date: Sat Apr 3 23:50:36 EDT 2010

Hello everyone.

I've been told that syntactically recursive functions can be written as
(while or for) loops. I've already experienced converting my recursive
Scheme functions to iterative Scheme functions when I wrote a _(while
condition)_ and a _(for init condition update)_ function, both syntactically
recursive of course. That said, whenever I have to transform a recursive
function to iterative, I try to "see" the recursion in the pattern of my
_while_ and _for_ functions. However, I find that I can't apply this method
to some algorithms.

Consider the LCSlength(s1, s2) function (pseudocode):

LCSlength(s1, s2){
    :: length(s1) == 0 OR length(s2) == 0, 0
    :: last(s1) == last(s2), 1 + LCSlength(minus-last(s1), minus-last(s2))
    :: else max(LCSlength(minus-last(s1), s2), LCSlength(s1,
minus-last(s2)))
    }

I can write this method iteratively but only up to the second condition. I
don't know how to handle the last condition in which the algorithm "branches
out" into two and takes the branch which grew taller. Iteration, it seems to
me, is very linear...

Or maybe I haven't been iterating enough yet? How do I go about this? Any
pointers will be much appreciated. Thank you very much.

-- 
Chad Estioco
BS Computer Science (ongoing)
University of the Philippines-Diliman
==============================
http://www.skytreader.net
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20100404/f8261a4d/attachment.html>

Posted on the users mailing list.