[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.lisp

Iterative factorial procedure in SICP

chong.franklin

2/10/2016 9:16:00 AM

This is a factorial procedure from SICP that generates a recursive process.

(define (factorial n)
(if (= n 1)
1
(* n (factorial (- n 1)))))

Now this is the same procedure, but generates an iterative process. Counter increments up to n and product multiplies itself by counter in each procedure call. When not in a block structure, fact-iter has a variable max-count which is actually n.

(define (factorial n)
(define (iter product counter)
(if (> counter n)
product
(iter (* counter product)
(+ counter 1))))
(iter 1 1))

I'm a little curious as to why we need counter, it doesn't really do anything but incrementing itself and using its value for testing the base case. as with the recursive process, can't we just do the same process while just adding an accumuator to make it iterative? For example:

(define (factorial n)
(define (fact-iter product n)
(if (= n 1)
product
(fact-iter (* n product)
(- n 1))))
(fact-iter 1 n))

So, this is still an iterative process, and I think a more obvious procedure than the first example.

However, there must be a reason why the book prefered the first example. So what is the advantage of the first iterative example over the second procedure?
4 Answers

Norbert_Paul

2/10/2016 1:09:00 PM

0

franklin wrote:
> This is a factorial procedure from SICP that generates a recursive process.
>
> (define (factorial n)
> (if (= n 1)
> 1
> (* n (factorial (- n 1)))))
>
> Now this is the same procedure, but generates an iterative process. Counter increments up to n and product multiplies itself by counter in each procedure call. When not in a block structure, fact-iter has a variable max-count which is actually n.
>
> (define (factorial n)
> (define (iter product counter)
> (if (> counter n)
> product
> (iter (* counter product)
> (+ counter 1))))
> (iter 1 1))
>
> I'm a little curious as to why we need counter, it doesn't really do anything but incrementing itself and using its value for testing the base case. as with the recursive process, can't we just do the same process while just adding an accumuator to make it iterative? For example:
>
> (define (factorial n)
> (define (fact-iter product n)
> (if (= n 1)
> product
> (fact-iter (* n product)
> (- n 1))))
> (fact-iter 1 n))
>
> So, this is still an iterative process, and I think a more obvious procedure than the first example.
>
> However, there must be a reason why the book prefered the first example. So what is the advantage of the first iterative example over the second procedure?

Without having tested if your second example is correct, both seem equivalent.
You merely rename counter to n and decrease it from n to 1.
So SICP's iteration does 1 * 2 * ... * n by incrementing counter
You seeminly do n * ... * 2 * 1 by decrementing n.
To me neither is more obvious than the other.

Dan Sommers

2/10/2016 1:40:00 PM

0

On Wed, 10 Feb 2016 14:09:19 +0100, Norbert_Paul wrote:

> franklin wrote:

>> (define (factorial n)
>> (define (iter product counter)
>> (if (> counter n)
>> product
>> (iter (* counter product)
>> (+ counter 1))))
>> (iter 1 1))

>> (define (factorial n)
>> (define (fact-iter product n)
>> (if (= n 1)
>> product
>> (fact-iter (* n product)
>> (- n 1))))
>> (fact-iter 1 n))

>> So, this is still an iterative process, and I think a more obvious
>> procedure than the first example.

>> However, there must be a reason why the book prefered the first
>> example. So what is the advantage of the first iterative example over
>> the second procedure?

> Without having tested if your second example is correct, both seem equivalent.
> You merely rename counter to n and decrease it from n to 1.
> So SICP's iteration does 1 * 2 * ... * n by incrementing counter
> You seeminly do n * ... * 2 * 1 by decrementing n.
> To me neither is more obvious than the other.

They give different results for (factorial 0).

chong.franklin

2/10/2016 2:02:00 PM

0

On Wednesday, February 10, 2016 at 9:43:15 PM UTC+8, Dan Sommers wrote:
> On Wed, 10 Feb 2016 14:09:19 +0100, Norbert_Paul wrote:
>
> > franklin wrote:
>
> >> (define (factorial n)
> >> (define (iter product counter)
> >> (if (> counter n)
> >> product
> >> (iter (* counter product)
> >> (+ counter 1))))
> >> (iter 1 1))
>
> >> (define (factorial n)
> >> (define (fact-iter product n)
> >> (if (= n 1)
> >> product
> >> (fact-iter (* n product)
> >> (- n 1))))
> >> (fact-iter 1 n))
>
> >> So, this is still an iterative process, and I think a more obvious
> >> procedure than the first example.
>
> >> However, there must be a reason why the book prefered the first
> >> example. So what is the advantage of the first iterative example over
> >> the second procedure?
>
> > Without having tested if your second example is correct, both seem equivalent.
> > You merely rename counter to n and decrease it from n to 1.
> > So SICP's iteration does 1 * 2 * ... * n by incrementing counter
> > You seeminly do n * ... * 2 * 1 by decrementing n.
> > To me neither is more obvious than the other.
>
> They give different results for (factorial 0).

That might be, but changing (= n 1) to (= n 0) fixes the problem.

Richard Fateman

2/11/2016 5:01:00 AM

0

On 2/10/2016 6:01 AM, franklin wrote:
> On Wednesday, February 10, 2016 at 9:43:15 PM UTC+8, Dan Sommers wrote:
>> On Wed, 10 Feb 2016 14:09:19 +0100, Norbert_Paul wrote:
>>
>>> franklin wrote:
>>
>>>> (define (factorial n)
>>>> (define (iter product counter)
>>>> (if (> counter n)
>>>> product
>>>> (iter (* counter product)
>>>> (+ counter 1))))
>>>> (iter 1 1))
>>
>>>> (define (factorial n)
>>>> (define (fact-iter product n)
>>>> (if (= n 1)
>>>> product
>>>> (fact-iter (* n product)
>>>> (- n 1))))
>>>> (fact-iter 1 n))
>>
>>>> So, this is still an iterative process, and I think a more obvious
>>>> procedure than the first example.

I think the idea was to illustrate
a framework with the separate counter so that the pattern would be
obvious, and might be used for computing other functions. There is
often some proxy for the counter though. Certainly here.
And in common lisp there are direct iterative constructs.

I think the point being made about iterative processes is fairly subtle
for someone just trying to learn to program in Lisp or Scheme.