[plt-scheme] Recursion to iteration

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.

On Sun, Apr 4, 2010 at 12:52 PM, Synx <plt at synx.us.to> wrote:

>
> Andrei Estioco wrote:
> > Hello everyone.
> >
> > I've been told that syntactically recursive functions can be written as
> > (while or for) loops.
>
> You've been told, but the reality is that syntactically tail recursive
> functions can be written using looping constructs, but not generally
> recursive ones.
>
> > 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)))
> >     }
>
> 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
>
> > I can write this method iteratively but only up to the second condition.
>
> 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.
>
> > Iteration, it seems to me, is very linear...
>
> 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:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>



-- 
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/6cf9fb6f/attachment.html>