>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.)<div>
<br></div><div>Oh...so, it will be the same even if the strings are reversed? I haven't thought of that. Thanks</div><div><br></div><div>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.</div>
<div><br></div><div>Thank you very much for this insight.<br><br><div class="gmail_quote">On Sun, Apr 4, 2010 at 7:18 AM, Stephen Bloch <span dir="ltr"><<a href="mailto:sbloch@adelphi.edu">sbloch@adelphi.edu</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div class="im">On Apr 4, 2010, at 1:19 AM, Andrei Estioco <<a href="mailto:chadestioco@gmail.com" target="_blank">chadestioco@gmail.com</a>> wrote:<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
(define (last lst)<br>
(cond<br>
[(empty? lst) empty]<br>
[(empty? (rest lst)) (first lst)]<br>
[else (last (rest lst))]))<br>
<br>
(define (minus-last lst)<br>
(cond<br>
[(empty? lst) empty]<br>
[(empty? (rest lst)) empty]<br>
[else (cons (first lst)<br>
(minus-last (rest lst)))]))<br>
</blockquote>
<br></div>
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.)<br>
<br>
<br>
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.)<div class="im">
<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
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?<br>
</blockquote>
<br></div>
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.<br>
<br>
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.<br>
<br>
Steve Bloch<br>
</blockquote></div><br><br clear="all"><br>-- <br>Chad Estioco<br>BS Computer Science (ongoing)<br>University of the Philippines-Diliman<br>==============================<br><a href="http://www.skytreader.net">http://www.skytreader.net</a><br>
</div>