CODEWITHSUNDEEP
iterationlispracketfactorialsicp
user4206400
user4206400

Reputation:

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

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?

Upvotes: 1

Views: 111

Answers (1)

Renzo
Renzo

Reputation: 27424

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))))

Upvotes: 2

Related Questions