473,837 Members | 1,735 Online

# Iteration for Factorials

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.

Oct 22 '07
59 5830
On Oct 22, 1:26 pm, Py-Fun <lorna.bu...@gm ail.comwrote:
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.
The following simple adder functions should give you an idea of how
recursion can be recast as iteration:

def acc(i):
'''i should be a positive integer'''
if i 0:
return i + acc(i - 1)
return 0

print "acc", acc(9)

def itt(i):
'''i should be a positive integer'''
out = 0

while i 0:
out += i
i = i - 1

return out

print "itt", itt(9)
...
Is it a "factorial" though?
Er, no. And neither is mine. You may want to google for the definition
of factorial! Here's a hint:

reduce(operator .mul, range(1, i + 1))

--
Anthony Roy
Oct 22 '07 #11
From the cookbook, this time.
It satisfies the requirements nicely ;)
http://aspn.activestate.com/ASPN/Coo.../Recipe/496691

def tail_recursion( g):
'''
Version of tail_recursion decorator using no stack-frame
inspection.
'''
loc_vars ={"in_loop":Fal se,"cnt":0}

def result(*args, **kwd):
loc_vars["cnt"]+=1
if not loc_vars["in_loop"]:
loc_vars["in_loop"] = True
while 1:
tc = g(*args,**kwd)
try:
qual, args, kwd = tc
if qual == 'continue':
continue
except (TypeError, ValueError):
loc_vars["in_loop"] = False
return tc
else:
if loc_vars["cnt"]%2==0:
return ('continue',arg s, kwd)
else:
return g(*args,**kwd)
return result
@tail_recursion
def factorial(n, acc=1):
"calculate a factorial"
if n == 0:
return acc
res = factorial(n-1, n*acc)
return res

Oct 22 '07 #12
Marco Mariani wrote:
From the cookbook, this time.
It satisfies the requirements nicely ;)
http://aspn.activestate.com/ASPN/Coo.../Recipe/496691
[... snip the ultimate general-purpose answer to the OP's question ...

I really hope that's a wink up there, Marco. The poor guy
was just trying to get his homework done!

:>

TJG
Oct 22 '07 #13
Tim Golden wrote:
> From the cookbook, this time.
It satisfies the requirements nicely ;)

http://aspn.activestate.com/ASPN/Coo.../Recipe/496691

[... snip the ultimate general-purpose answer to the OP's question ...

I really hope that's a wink up there, Marco.
The wink is in the second line of my post... more for the "do the least
amount of work to meet the requirements" people that for the OP
The poor guy was just trying to get his homework done!
I don't see how my answer is in any way worse than those based on
lambda. Maybe I'm just envious because when I was his age I couldn't
google for answers. He should at least be able to do that, shouldn't he?
But wait. That would mean understanding what a factorial is. That would
require a second search, or a textbook, or an understanding of
arithmetics before programming with or without recursion. Should we
blame the teachers?
Oct 22 '07 #14
On Oct 22, 8:26 am, Py-Fun <lorna.bu...@gm ail.comwrote:
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.
def fac_btt(num):
total = 1
if num 1:
for i in range(1, num+1):
total *= i

Oct 22 '07 #15
On Oct 22, 8:02 am, vimal <cool.vimalsm.. .@gmail.comwrot e:
On Oct 22, 5:43 pm, Marco Mariani <ma...@sferacar ta.comwrote:
Py-Fun wrote:
def itforfact(n):
while n<100:
print n
n+1
n = input("Please enter a number below 100")
You function should probably return something. After that, you can see
what happens with the result you get.

i am just suggesting u an idea
but i dont know it satisfies ur needs

x=10
def cal_range(10)
for i in range(10):
print 2**i
Maybe a little math refresher would be good for those trying to post
suggestions.

"Factorial of N" means "the product of 1 x 2 x 3 x ... x N", and is
shown symbolically as "N!".

(Factorial is only defined for nonnegative numbers, and for reasons
that go beyond this little note, just know that 0! = 1.)

In Python, a fully expanded factorial for values >= 1 would be:

2! = 1 * 2
5! = 1 * 2 * 3 * 4 * 5
8! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8

Here is an example routine showing iteration, that prints these
expressions:
def print_factorial (n):
print str(n)+"! =",
print "1",
t = 2
while t <= n:
print "*",t,
t += 1
print

Perhaps this example will give you some ideas on how to approach your
problem.
-- Paul

Oct 22 '07 #16
Marco Mariani wrote:
Tim Golden wrote:
>> From the cookbook, this time.
It satisfies the requirements nicely ;)

http://aspn.activestate.com/ASPN/Coo.../Recipe/496691
[... snip the ultimate general-purpose answer to the OP's question ...

I really hope that's a wink up there, Marco.

The wink is in the second line of my post...
I did see it :)
>The poor guy was just trying to get his homework done!

I don't see how my answer is in any way worse than those based on
lambda.
Nor do I. I was just joking with a colleague that the guy
just wanted a bit of help (which he did get, in fact from
several sources) and then out came the lambda and the
decorator. It's only a moment before the metaclass and
the Twisted solution come along. :)
(It's like watching a convention of lisp programmers --
ducks, runs for cover)

TJG
Oct 22 '07 #17
On Oct 22, 7:50 am, Duncan Booth <duncan.bo...@i nvalid.invalidw rote:
Py-Fun <lorna.bu...@gm ail.comwrote:
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.

This version avoids doing anything fancier than adding 1, so it should be
simple enough for anyone:

def factorial(e):
a = 1
for b in range(e):
c = 0
for j in range(b, -1, -1):
for d in range(a):
c += 1
a = c
return a
Not simple enough for my taste:
>>import gmpy
gmpy.fac(10 )
mpz(3628800)

Oct 22 '07 #18
"me********@aol .com" <me********@aol .comwrites:
On Oct 22, 7:50 am, Duncan Booth <duncan.bo...@i nvalid.invalidw rote:
>Py-Fun <lorna.bu...@gm ail.comwrote:
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.

This version avoids doing anything fancier than adding 1, so it should be
simple enough for anyone:

def factorial(e):
a = 1
for b in range(e):
c = 0
for j in range(b, -1, -1):
for d in range(a):
c += 1
a = c
return a

Not simple enough for my taste:
>>>import gmpy
gmpy.fac(1 0)
mpz(3628800)
I haven't followed all this thread, but has anyone yet done:

import operator
def fact(x):
return reduce(operator .mul, xrange(1,x))
Oct 22 '07 #19
On Oct 22, 1:35 pm, Paul Rudin <paul.nos...@ru din.co.ukwrote:
"mensana...@aol .com" <mensana...@aol .comwrites:
On Oct 22, 7:50 am, Duncan Booth <duncan.bo...@i nvalid.invalidw rote:
Py-Fun <lorna.bu...@gm ail.comwrote:
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.
This version avoids doing anything fancier than adding 1, so it should be
simple enough for anyone:
def factorial(e):
a = 1
for b in range(e):
c = 0
for j in range(b, -1, -1):
for d in range(a):
c += 1
a = c
return a
Not simple enough for my taste:
>>import gmpy
gmpy.fac(10 )
mpz(3628800)

I haven't followed all this thread, but has anyone yet done:

import operator
def fact(x):
return reduce(operator .mul, xrange(1,x))
I hope not.
>>import operator
def fact(x):
return reduce(operator .mul,xrange(1,x ))
>>fact(3)
2
>>fact(2)
1
>>fact(1)
Traceback (most recent call last):
File "<pyshell#1 0>", line 1, in <module>
fact(1)
File "<pyshell#7 >", line 2, in fact
return reduce(operator .mul,xrange(1,x ))
TypeError: reduce() of empty sequence with no initial value
>>fact(0)
Traceback (most recent call last):
File "<pyshell#1 1>", line 1, in <module>
fact(0)
File "<pyshell#7 >", line 2, in fact
return reduce(operator .mul,xrange(1,x ))
TypeError: reduce() of empty sequence with no initial value

I think you need to make it a bit more complicated.

Oct 22 '07 #20

This thread has been closed and replies have been disabled. Please start a new discussion.