Beginner recursion question
Eric
I've been curious about Lisp since the eighties where my college
Fortran instructor was a Lisp developer. I'm learning Scheme from
"The Little Schemer" book, I've also looked at a view of MIT's
"Structure and Interpretation of Computer Programs" lecture series on
archive.org.
In that series, Dr. Sussman, shows examples of 2 methods to do
addition, both use recursion. One adds 1 to the result of calling
itself multiple times. Dr. Sussman shows how this tends to make the
program bigger. What struck me, was the technique that Dr. Sussman
demonstrates to be less efficient seems to be precisely the technique
being taught in "The Little Schemer" book, although I'm admittedly
only 2/3 of the way through the book. Am I not understanding
something correctly?
-Eric
Pascal J. Bourguignon
Sometimes, the most efficient algorithm is not the simpliest one.
And sometimes it doesn't matter.
--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.
WJ
Using recursion to perform addition is simply a training exercise.
In the real world, recursion is used for more sensible tasks.
guile> (define (fac n) (if (< n 2) 1 (* n (fac (- n 1)))))
guile> (fac 9)
362880
guile> (iota 15)
(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14)
guile> (define (pairs x)
(if (< (length x) 2)
'()
(cons (take x 2) (pairs (cddr x)))))
guile> (pairs (iota 15))
((0 1) (2 3) (4 5) (6 7) (8 9) (10 11) (12 13))
Fyndhorn Elder
> Eric wrote:
>
>> Hello,
>>
>> I've been curious about Lisp since the eighties where my college
>> Fortran instructor was a Lisp developer. I'm learning Scheme from
>> "The Little Schemer" book, I've also looked at a view of MIT's
>> "Structure and Interpretation of Computer Programs" lecture series on
>> archive.org.
>>
>> In that series, Dr. Sussman, shows examples of 2 methods to do
>> addition, both use recursion. One adds 1 to the result of calling
>> itself multiple times. Dr. Sussman shows how this tends to make the
>> program bigger. What struck me, was the technique that Dr. Sussman
>> demonstrates to be less efficient seems to be precisely the technique
>> being taught in "The Little Schemer" book, although I'm admittedly
>> only 2/3 of the way through the book. Am I not understanding
>> something correctly?
>>
>> -Eric
One uses a result variable and one uses recursion. You can do things
with do also.
tail-recursion is using the return value of the function multiple times
so the result gets reinstantiated after unrolling the stack.
Your stack does not get set in iteration, you use the set! native
method to reinstantiate your result parameter.
One of my favorites is using do with things like lists and indexes
e.g. both
(do ((li start-list (cdr li))
(i 0 (+ i 1)))
((null? li) #f)
(list-ref li i)))
This method is faster than recursion and iteration most of the time.
If you want to do it with continuations you call a reference which is ,
(I think) not on the stack unless you want it. you have to combine
things here.
It might also be wise to use #f and #t as above, which are dealt with as
booleans in scheme and are evaluated faster than say a list or symbol.
HTH,
FE
raof01
> If you want to do it with continuations you call a reference which is ,
> (I think) not on the stack unless you want it. you have to combine
> things here.