[plt-scheme] Recursion to iteration

>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.)

Oh...so, it will be the same even if the strings are reversed? I haven't
thought of that. Thanks

The big picture is that I am trying to learn dynamic programming. As I am
still at that stage when things seem to work like magic, I haven't tinkered
with the algorithms yet. I've coded it "verbatim" as my reference said,
which is to work from the last character to the first, at the cost of
efficiency issues.

Thank you very much for this insight.

On Sun, Apr 4, 2010 at 7:18 AM, Stephen Bloch <sbloch at adelphi.edu> wrote:

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



-- 
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/20100405/7ad89078/attachment.html>