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