My quick Scheme code:<br><br>But some notes first:<br>1) Might&#39;ve rewritten functions already defined<br>2) I&#39;m aware of it&#39;s inefficiency as repeated calls to _minus-last_ goes through the list repeatedly<br>3) I represented strings as list as I haven&#39;t had any experience with Scheme strings yet.<br>

<br>The code:<br><br>(define (last lst)<br>  (cond<br>    [(empty? lst) empty]<br>    [(empty? (rest lst)) (first lst)]<br>    [else (last (rest lst))]))<br><br>(define (minus-last lst)<br>  (cond<br>    [(empty? lst) empty]<br>

    [(empty? (rest lst)) empty]<br>    [else (cons (first lst)<br>                (minus-last (rest lst)))]))<br><br>(define (lcs lst1 lst2)<br>  (local ((define last_lst1 (last lst1))<br>          (define last_lst2 (last lst2))<br>

          <br>          (define (compute_length)<br>            (cond<br>              [(or (= (length lst1) 0)<br>                   (= (length lst2) 0))<br>               0]<br>              [(equal? last_lst1 last_lst2) (+ 1 (lcs (minus-last lst1)<br>

                                                      (minus-last lst2)))]<br>              [else (max (lcs (minus-last lst1) lst2)<br>                         (lcs lst1 (minus-last lst2)))])))<br>    (compute_length)))<br>


<br>
&gt;You&#39;ve been told, but the reality is that syntactically tail recursive<br>
&gt;functions can be written using looping constructs, but not generally<br>
&gt;recursive ones.<br><br>That&#39;s enlightening. Thanks.<br><br>&gt;What you have is a generally recursive algorithm. It&#39;s possible to write<br>
&gt;this iteratively, but not possible to write it without a stack of some<br>&gt;sort. What you could do to make it iterative is use an explicit stack<br>&gt;onto which you pushed the pending values while you calculated the next<br>

&gt;recursion level, and once you&#39;re done you just pop off the stack, apply,<br>&gt;and keep going through the loop.<br>
&gt;<br>&gt;But that&#39;s a bad idea.<br>
&gt;<br>&gt;A really, really bad idea.<br><br>I&#39;m actually implementing this in Java. I&#39;m just &quot;pseudocoding&quot; in Scheme, to gain a grasp on the algorithm. Using an explicit stack won&#39;t really reduce my runtime right? My bad. I hit a dead end. Thanks for the insight anyway.<br>

<br><div class="gmail_quote">On Sun, Apr 4, 2010 at 12:52 PM, Synx <span dir="ltr">&lt;<a href="mailto:plt@synx.us.to">plt@synx.us.to</a>&gt;</span> wrote:<br><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"><br>
Andrei Estioco wrote:<br>
&gt; Hello everyone.<br>
&gt;<br>
&gt; I&#39;ve been told that syntactically recursive functions can be written as<br>
&gt; (while or for) loops.<br>
<br>
</div>You&#39;ve been told, but the reality is that syntactically tail recursive<br>
functions can be written using looping constructs, but not generally<br>
recursive ones.<br>
<div class="im"><br>
&gt; Consider the LCSlength(s1, s2) function (pseudocode):<br>
&gt;<br>
&gt; LCSlength(s1, s2){<br>
&gt;     :: length(s1) == 0 OR length(s2) == 0, 0<br>
&gt;     :: last(s1) == last(s2), 1 + LCSlength(minus-last(s1), minus-last(s2))<br>
&gt;     :: else max(LCSlength(minus-last(s1), s2), LCSlength(s1,<br>
&gt; minus-last(s2)))<br>
&gt;     }<br>
<br>
</div>Might be better if you used scheme pseudocode<br>
<br>
<br>
(define (minus l)<br>
  ; what&#39;s this supposed to do?<br>
  l)<br>
<br>
(define (lcs-length s1 s2)<br>
  (cond<br>
    ((or (null? s1) (null? s2))<br>
     0)<br>
    ((= (car s1) (car s2))<br>
     (+ 1 (lcs-length (minus (cdr s1)) (minus (cdr s2)))))<br>
    (else<br>
     (max (lcs-length (minus (cdr s1)) (cdr s2))<br>
          (lcs-length (cdr s1) (minus (cdr s2)))))))<br>
<br>
...because that code actually compiles! :3<br>
<div class="im"><br>
&gt; I can write this method iteratively but only up to the second condition.<br>
<br>
</div>What you have is a generally recursive algorithm. It&#39;s possible to write<br>
this iteratively, but not possible to write it without a stack of some<br>
sort. What you could do to make it iterative is use an explicit stack<br>
onto which you pushed the pending values while you calculated the next<br>
recursion level, and once you&#39;re done you just pop off the stack, apply,<br>
and keep going through the loop.<br>
<br>
But that&#39;s a bad idea.<br>
<br>
A really, really bad idea.<br>
<br>
Because scheme is *really* good at doing exactly that automatically. The<br>
way to get scheme to manage a stack for you, and ensure that only what<br>
is needed is on it at any given point is to just write the procedure<br>
recursively, and forget about any explicit stack yourself.<br>
<div class="im"><br>
&gt; Iteration, it seems to me, is very linear...<br>
<br>
</div>I don&#39;t generally consider &quot;branching&quot; style algorithms to be iteration,<br>
even though it is possible to implement them with only iteration<br>
constructs and an explicit stack. That might be a matter of opinion<br>
though. It&#39;s probably more accurate if you referred to things as tail<br>
recursive and uh... not tail-recursive, because linear doesn&#39;t really<br>
specify anything about the nature of the algorithm. Any<br>
Turing-compatible algorithm is going to be &quot;linear&quot; whether<br>
tail-recursive or not.<br>
_________________________________________________<br>
  For list-related administrative tasks:<br>
  <a href="http://list.cs.brown.edu/mailman/listinfo/plt-scheme" target="_blank">http://list.cs.brown.edu/mailman/listinfo/plt-scheme</a><br>
</blockquote></div><br><br clear="all"><br>-- <br>Chad Estioco<br>BS Computer Science (ongoing)<br>University of the Philippines-Diliman<br>==============================<br><a href="http://www.skytreader.net">http://www.skytreader.net</a><br>