SICP - Is my recursive definition of an iterative process for factorial bad?

Question

I am studying the awesome book SICP. Despite being great, it is a really tough book. I am having problems with the long tail recursion,id est, a recursion definition for an iterative process. The book presents this iterative procedure for factorial:

(define (factorial n)
  (fact-iter 1 1 n))
(define (fact-iter product counter max-count)
  (if (> counter max-count)
      product
      (fact-iter (* counter product)
                 (+ counter 1)
                 max-count)))

I tried doing one approach without looking at the book example. I got this:

(define (factorial n)
  (factorial-iter n 1 n))

(define (factorial-iter a product counter)
  (if (= counter 0)
      product
      (factorial-iter (- a 1)
                      (* product a)
                      (- counter 1))))

Is my approach wrong in some sense?

Renzo Renzo · Accepted Answer · 2016-09-05T18:48:07

There is nothing wrong in your approach, it calculates correctly the factorial, there is only something superfluous. You can note that the two variables a and counter have always the same value since they are updated always in the same way. So you can get rid of one of them, and simplify your function in this way:

(define (factorial n)
  (factorial-iter n 1))

(define (factorial-iter a product)
  (if (= a 0)
      product
      (factorial-iter (- a 1)
                      (* product a))))

Finally, to stay on the safe side, you can change the test for the termination to see if a is less than or equal to 0, so the function will not loop endless with a negative argument:

(define (factorial-iter a product)
  (if (<= a 0)
      product
      (factorial-iter (- a 1)
                      (* product a))))

SICP - Is my recursive definition of an iterative process for factorial bad?

1 Answers