[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>