Iteration for Factorials

[Michael J. Fromberger]

In article <1193055966.362489.252080 at v29g2000prd.googlegroups.com>,
 Py-Fun <lorna.burns at gmail.com> wrote:

> I'm stuck trying to write a function that generates a factorial of a
> number using iteration and not recursion.  Any simple ideas would be
> appreciated.


Well, first think about the recursive implementation:

  def fact(n):
    if n > 0:
      return n * fact(n - 1)
    else:
      return 1

To turn this into an iterative computation, you must first get rid of 
the deferred operations -- in this case, the multiplication step after 
the recursive call to fact(n - 1).  

Since multiplication commutes, we can re-write this recursion to keep an 
accumulating parameter instead of deferring the operation:

  def fact2(n, acc = 1):
    if n > 0:
      return fact2(n - 1, acc * n)
    else:
      return acc

This is a little bit better, because now the recursive call is in tail 
position, and so in principle no state needs to be saved across 
recursive calls:  Once the inner call to fact2 is complete, its value is 
simply returned.  But we're not done yet, because Python _does_ save 
state across recursive calls, even in this construction.

By a gentle twist of perspective, the inner call to "fact2(n - 1, acc * 
n)" is really just a kind of "jump" back to the beginning of the 
function.  In another (hypothetical) language, you might write it like 
this:

  # Not legal Python code.
  def fact3(n, acc = 1):
    TOP: 
      if n > 0
        n = n - 1
        acc = acc * n
        goto TOP
      else:
        return acc

Naturally, of course, Python does not provide a "goto" statement.  But 
it does have one that's similar:

  while TEST: BODY

is equivalent in meaning to the pseudo-code:

  X: if TEST: 
       BODY  
       goto X

Can you now see how you would re-write "fact3" into legal Python code,
using this equivalence?  Once you have done so, you will also be able to
get rid of the extra accumulating parameter, and then you will have what 
you wanted.

I hope this helps.

Cheers,
-M

-- 
Michael J. Fromberger             | Lecturer, Dept. of Computer Science
http://www.dartmouth.edu/~sting/  | Dartmouth College, Hanover, NH, USA