[plt-scheme] Recursion to iteration

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.