In article <[EMAIL PROTECTED]>,
Py-Fun <[EMAIL PROTECTED]> 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
--
http://mail.python.org/mailman/listinfo/python-list
