My quick Scheme code: But some notes first: 1) Might've rewritten functions already defined 2) I'm aware of it's inefficiency as repeated calls to _minus-last_ goes through the list repeatedly 3) I represented strings as list as I haven't had any experience with Scheme strings yet. The code: (define (last lst) (cond [(empty? lst) empty] [(empty? (rest lst)) (first lst)] [else (last (rest lst))])) (define (minus-last lst) (cond [(empty? lst) empty] [(empty? (rest lst)) empty] [else (cons (first lst) (minus-last (rest lst)))])) (define (lcs lst1 lst2) (local ((define last_lst1 (last lst1)) (define last_lst2 (last lst2)) (define (compute_length) (cond [(or (= (length lst1) 0) (= (length lst2) 0)) 0] [(equal? last_lst1 last_lst2) (+ 1 (lcs (minus-last lst1) (minus-last lst2)))] [else (max (lcs (minus-last lst1) lst2) (lcs lst1 (minus-last lst2)))]))) (compute_length))) >You've been told, but the reality is that syntactically tail recursive >functions can be written using looping constructs, but not generally >recursive ones. That's enlightening. Thanks. >What you have is a generally recursive algorithm. It's possible to write >this iteratively, but not possible to write it without a stack of some >sort. What you could do to make it iterative is use an explicit stack >onto which you pushed the pending values while you calculated the next >recursion level, and once you're done you just pop off the stack, apply, >and keep going through the loop. > >But that's a bad idea. > >A really, really bad idea. I'm actually implementing this in Java. I'm just "pseudocoding" in Scheme, to gain a grasp on the algorithm. Using an explicit stack won't really reduce my runtime right? My bad. I hit a dead end. Thanks for the insight anyway. <div class="gmail_quote">On Sun, Apr 4, 2010 at 12:52 PM, Synx <<a href="mailto:plt@synx.us.to">plt@synx.us.to</a>> wrote: <blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"> <div class="im"> Andrei Estioco wrote: > Hello everyone. > > I've been told that syntactically recursive functions can be written as > (while or for) loops. </div>You've been told, but the reality is that syntactically tail recursive functions can be written using looping constructs, but not generally recursive ones. <div class="im"> > 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))) > } </div>Might be better if you used scheme pseudocode (define (minus l) ; what's this supposed to do? l) (define (lcs-length s1 s2) (cond ((or (null? s1) (null? s2)) 0) ((= (car s1) (car s2)) (+ 1 (lcs-length (minus (cdr s1)) (minus (cdr s2))))) (else (max (lcs-length (minus (cdr s1)) (cdr s2)) (lcs-length (cdr s1) (minus (cdr s2))))))) ...because that code actually compiles! :3 <div class="im"> > I can write this method iteratively but only up to the second condition. </div>What you have is a generally recursive algorithm. It's possible to write this iteratively, but not possible to write it without a stack of some sort. What you could do to make it iterative is use an explicit stack onto which you pushed the pending values while you calculated the next recursion level, and once you're done you just pop off the stack, apply, and keep going through the loop. But that's a bad idea. A really, really bad idea. Because scheme is *really* good at doing exactly that automatically. The way to get scheme to manage a stack for you, and ensure that only what is needed is on it at any given point is to just write the procedure recursively, and forget about any explicit stack yourself. <div class="im"> > Iteration, it seems to me, is very linear... </div>I don't generally consider "branching" style algorithms to be iteration, even though it is possible to implement them with only iteration constructs and an explicit stack. That might be a matter of opinion though. It's probably more accurate if you referred to things as tail recursive and uh... not tail-recursive, because linear doesn't really specify anything about the nature of the algorithm. Any Turing-compatible algorithm is going to be "linear" whether tail-recursive or not. _________________________________________________ For list-related administrative tasks: <a href="http://list.cs.brown.edu/mailman/listinfo/plt-scheme" target="_blank">http://list.cs.brown.edu/mailman/listinfo/plt-scheme</a> </blockquote></div> -- Chad Estioco BS Computer Science (ongoing) University of the Philippines-Diliman ============================== <a href="http://www.skytreader.net">http://www.skytreader.net</a>