Scheme For Enlightenment Part Two - More Factorials

The dreaded Scheme factorial example is continued.

Consider this factorial version, which uses a do loop instead of recursion. It has two extra variables, is a little longer, and what is going on anyway? One expects the first example to be better all around. But if one feeds this version 1000, it quickly spits out all 2,568 digits of the answer. Since it works with bigger numbers, and is as quick or quicker for smaller numbers, it's better, right?

(define (factorial x)
  (do ((count 1 (+ count 1))
       (product 1 (* count product)))
      ((> count x) product)))

The second line starts the do loop. The variable count starts at one, and is incremented by one each time through the loop. In the third line, the variable product also starts at one (same loop), and is multiplied by the variable count each time through the loop. The forth line says that the loop continues until count is more than x (the parameter). When all is finished, the value of product is returned. Let's walk an example.

(factorial 3)

Count starts at 1, product starts at one multiplied by count which is also one, and so is 1. The parameter x, which is 3 is compared to count. Since count is not larger than the parameter x, the body, which doesn't have anything in it, is executed. One is added to count, resulting in 2. This is multiplied by product, and product gets the answer, (* 1 2) is 2. count, which is 2, is compared to x, which is 3. Count is still not bigger than 3, so the loop restarts again. One is added to count, and so it now has the value 3. The variable product, 2 is multiplied by count, 3, and the result, 6 is assigned to product. Count, 3, is compared with x, 3, and it isn't bigger yet, so you'd think that the loop continues. However, that's not what it does, and we know this because the answer isn't 24, it's 6. Somehow, count gets incremented so that it is greater than 3, but product is not multiplied by 4. This mystery is solved, i think, by reading the manual. From the Guile Reference, section 5.11.4, The test expression is a termination condition. Looping stops when the test is true. It's evaluated before running the body each time, so if it's true the first time then body is not run at all. So the order of operations isn't exactly the way that i've outlined it.

So, in theory, the pure recursive version is simpler and better. In practice the loop version is faster and gives correct results for a wider range of input. What's the difference between theory and practice? In theory, they are the same...