Iterative factorial procedure in SICP

Question

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?

@reto I did. And I believe my second example is still iterative because I still pass on all information to the parameters needed to perform the procedure. — lightning_missile
The only difference between the two seems to be that the first one counts up, and the second counts down. It makes no difference which one you use. Btw. you should not use the same name for n in the inner function. That's needlesly confusing. — jkiiski
There is no significant difference between the two formulations, as @jkiiski noted, but you should change (= n 1) in (= n 0) in your function, otherwise (factorial 0) causes an endless loop. — Renzo
There's no advantage to either - the first views the factorial as 1 * 2 * ... * n and the second as n * (n - 1) * ... * 1. The first is more "loop-like" and the second more "recursion-like", in my opinion. — molbdnilo

Sylwester Sylwester · Accepted Answer · 2016-02-10T09:58:32

Your two iterative versions are the same except one counts up and compares with a free variable n while the other counts down and compares to a constant.

It won't make much difference in speed so I guess the one you think you should go with the one that is more clear in it's intention. Some people might prefer the steps going up.

Sometimes you may choose the order wisely though. If you were to make a list of the numbers instead you would have chosen the steps in the opposite order of your wanted resulting list to be able to keep it iterative:

(define (make-range to)
  (define (aux to acc)
    (if (> 0 to)
        acc
        (aux (- to 1) (cons to acc))))
  (aux to '()))

(define (make-reverse-range start)
  (define (aux n acc)
    (if (> n start)
        acc
        (aux (+ n 1) (cons n acc))))
  (aux 0 '()))

(make-range 10)          ; ==> (0 1 2 3 4 5 6 7 8 9 10)
(make-reverse-range 10)  ; ==> (10 9 8 7 6 5 4 3 2 1 0)

Iterative factorial procedure in SICP

1 Answers