Hello, i have the following procedures that are used for adding 2
positive integers where inc increases its argument by 1 and dec
decreases its argument by 1:
(define (+ a b)
(if (= a 0)
b
(inc (+ (dec a) b))))
(define (+ a b)
(if (= a 0)
b
(+ (dec a) (inc b))))
Could someone please explain whether these procedures are iterative or
recursive and why? It would be much appreciated...
-Daniel
Daniel Eckerd <·······@unh.edu> wrote in message
······················@unh.edu...
>Hello, i have the following procedures that are used for adding 2
>positive integers where inc increases its argument by 1 and dec
>decreases its argument by 1:
>
>(define (+ a b)
>(if (= a 0)
>b
>(inc (+ (dec a) b))))
>
>
>(define (+ a b)
>(if (= a 0)
>b
>(+ (dec a) (inc b))))
>
>
>Could someone please explain whether these procedures are iterative or
>recursive and why? It would be much appreciated...
Technically speaking, they are both `recursive' procedures: they call
themselves. But one evolves a `recursive' process whereas the other
evolves an `iterative' process (assuming proper tail-recursion).
The key to telling which is which is to look at the recursive call. If
the result of the recursive call is going to be used as an argument
or manipulated (like being incremented), then you need to `come
back' and finish the computation. This means that you have a chain
of pending computations that gets deeper each time around
If the result of the recursive call is simply going to be returned as
the answer, then you don't need to `come back and finish', so there
are no pending computations.
Consider adding 3 and 2 with your two programs. One works like this:
(+ 3 2) =
(+ 2 3) =
(+ 1 4) =
(+ 0 5) =
5
Except for the base case, the result of each recursive call is
the result of another recursive call. The program just goes around
in a loop until it gets the answer. This is an iterative process.
the other works like this:
(+ 3 2) =
(+ 1 (+ 2 2)) =
(+ 1 (+ 1 (+ 1 2))) =
(+ 1 (+ 1 (+ 1 (+ 0 2)))) =
(+ 1 (+ 1 (+ 1 2))) =
(+ 1 (+ 1 3)) =
(+ 1 4) =
5
In this case, each recusive call produces a result which
needs to be combined with other information to produce
a result. The program saves up pending computations until
it reaches the base case. This is a recursive process.
I hope this helps
Thanks guys, I had an idea of what recursion was, but when i looked at
some examples of recursion and iteration, it seemed like the two were
the same in some instances! Anyway, does anyone know of any websites
where they have lots of examples of both so i could better distigniush
them? Thanks again.
-Danniel
cdm wrote:
>
> Daniel Eckerd <·······@unh.edu> wrote in message
> ······················@unh.edu...
> >Hello, i have the following procedures that are used for adding 2
> >positive integers where inc increases its argument by 1 and dec
> >decreases its argument by 1:
> >
> >(define (+ a b)
> >(if (= a 0)
> >b
> >(inc (+ (dec a) b))))
> >
> >
> >(define (+ a b)
> >(if (= a 0)
> >b
> >(+ (dec a) (inc b))))
> >
> >
> >Could someone please explain whether these procedures are iterative or
> >recursive and why? It would be much appreciated...
>
> Technically speaking, they are both `recursive' procedures: they call
> themselves. But one evolves a `recursive' process whereas the other
> evolves an `iterative' process (assuming proper tail-recursion).
>
> The key to telling which is which is to look at the recursive call. If
> the result of the recursive call is going to be used as an argument
> or manipulated (like being incremented), then you need to `come
> back' and finish the computation. This means that you have a chain
> of pending computations that gets deeper each time around
>
> If the result of the recursive call is simply going to be returned as
> the answer, then you don't need to `come back and finish', so there
> are no pending computations.
>
> Consider adding 3 and 2 with your two programs. One works like this:
> (+ 3 2) =
> (+ 2 3) =
> (+ 1 4) =
> (+ 0 5) =
> 5
>
> Except for the base case, the result of each recursive call is
> the result of another recursive call. The program just goes around
> in a loop until it gets the answer. This is an iterative process.
>
> the other works like this:
> (+ 3 2) =
> (+ 1 (+ 2 2)) =
> (+ 1 (+ 1 (+ 1 2))) =
> (+ 1 (+ 1 (+ 1 (+ 0 2)))) =
> (+ 1 (+ 1 (+ 1 2))) =
> (+ 1 (+ 1 3)) =
> (+ 1 4) =
> 5
>
> In this case, each recusive call produces a result which
> needs to be combined with other information to produce
> a result. The program saves up pending computations until
> it reaches the base case. This is a recursive process.
>
> I hope this helps
OOPS, i forgot, inc and dec were not included as definitions, here they
are :
(define (inc x) (+ x 1)
(define (dec x) (- x 1)
Daniel Eckerd wrote:
>
> Hello, i have the following procedures that are used for adding 2
> positive integers where inc increases its argument by 1 and dec
> decreases its argument by 1:
>
> (define (+ a b)
> (if (= a 0)
> b
> (inc (+ (dec a) b))))
>
> (define (+ a b)
> (if (= a 0)
> b
> (+ (dec a) (inc b))))
>
> Could someone please explain whether these procedures are iterative or
> recursive and why? It would be much appreciated...
>
> -Daniel
Daniel Eckerd <·······@unh.edu> writes:
> OOPS, i forgot, inc and dec were not included as definitions, here
> they are :
>
> (define (inc x) (+ x 1)
> (define (dec x) (- x 1)
I'm curious, which of the two redefinitions of `+' is meant to be used
in the definition of `inc'?
> Daniel Eckerd wrote:
...
> > (define (+ a b)
> > (if (= a 0)
> > b
> > (inc (+ (dec a) b))))
> >
> > (define (+ a b)
> > (if (= a 0)
> > b
> > (+ (dec a) (inc b))))
...
Put all this code in a file, add a couple of parentheses and proper
indentation (you should indent even if your instructor doesn't) and
load it into a Scheme interpreter. You will get a `+' that loops as
long as there is room for a deep recursion:
(+ 1 1) =>
(+ 0 (+ 1 1)) =>
(+ 0 (+ 0 (+ 1 1))) =>
(+ 0 (+ 0 (+ 0 (+ 1 1)))) =>
...
See? The latter `+� is the one that remains in effect and is used by
`inc' while `dec' uses the Scheme `-'. The call `(+ 1 1)' gets
rewritten as `(+ 0 (inc 1))' gets rewritten as `(+ 0 (+ 1 1))' and
then you keep rewriting the innermost call until it becomes a constant
or the stack overflows, that is, the expression becomes too long. The
original problem appears as a subproblem during the recursion.
Hope this helps,
--
Jussi
In article <·················@unh.edu>, Daniel Eckerd <·······@unh.edu> wrote:
>OOPS, i forgot, inc and dec were not included as definitions, here they
>are :
>
>(define (inc x) (+ x 1)
>(define (dec x) (- x 1)
>
>Daniel Eckerd wrote:
>>
>> Hello, i have the following procedures that are used for adding 2
>> positive integers where inc increases its argument by 1 and dec
>> decreases its argument by 1:
>>
>> (define (+ a b)
>> (if (= a 0)
>> b
>> (inc (+ (dec a) b))))
>>
>> (define (+ a b)
>> (if (= a 0)
>> b
>> (+ (dec a) (inc b))))
>>
>> Could someone please explain whether these procedures are iterative or
>> recursive and why? It would be much appreciated...
They're recursive, since they work by calling themselves. Isn't that the
definition of recursion?
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
In article <················@burlma1-snr2>,
Barry Margolin <······@bbnplanet.com> wrote:
> In article <·················@unh.edu>, Daniel Eckerd <·······@unh.edu>
wrote:
> >OOPS, i forgot, inc and dec were not included as definitions, here they
> >are :
> >
> >(define (inc x) (+ x 1)
> >(define (dec x) (- x 1)
> >
> >Daniel Eckerd wrote:
> >>
> >> Hello, i have the following procedures that are used for adding 2
> >> positive integers where inc increases its argument by 1 and dec
> >> decreases its argument by 1:
> >>
> >> (define (+ a b)
> >> (if (= a 0)
> >> b
> >> (inc (+ (dec a) b))))
> >>
> >> (define (+ a b)
> >> (if (= a 0)
> >> b
> >> (+ (dec a) (inc b))))
> >>
> >> Could someone please explain whether these procedures are iterative or
> >> recursive and why? It would be much appreciated...
>
> They're recursive, since they work by calling themselves. Isn't that the
> definition of recursion?
But the second is tail-recursive, so Scheme will transform it into an
iterative process.
This is an exercise from SICP.
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own