[plt-scheme] Recursion to iteration

On Apr 4, 2010, at 1:19 AM, Andrei Estioco <chadestioco at gmail.com>  
wrote:

> (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)))]))

Just a note for optimization later: is there a good reason for looking  
at the last and all-but-last, both of which take linear time, rather  
than the first and all-but-first, both of which take constant time in  
Scheme?  (If you're using Java, you should probably use LinkedLists,  
which IIRC are doubly linked so you can get at whichever end you wish  
in constant time.)


As has already been pointed out, not all recursion can be  
straightforwardly translated into iteration (although all iteration  
CAN be straightforwardly translated into recursion).  Doubly-recursive  
algorithms like this are the classic examples.  (Another of my  
favorites is pattern-matching with a "*" wild-card.)

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

No, it almost certainly won't, and it'll probably introduce a lot of  
bugs that the implementers of Scheme and Java have already fixed.

You can do this problem perfectly well in Java, or C++, or any  
language that supports recursion.  Where Scheme beats these other  
languages (in performance) is tail-calls, and this algorithm doesn't  
have a lot of tail calls.

Steve Bloch