# Iteration for Factorials

Discussion in 'Python' started by Py-Fun, Oct 22, 2007.

1. ### Py-FunGuest

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.

Py-Fun, Oct 22, 2007

2. ### Diez B. RoggischGuest

Py-Fun 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.

Show us your attempts, and we might suggest a fix. Because otherwise this
sounds suspiciously like homework.

Diez

Diez B. Roggisch, Oct 22, 2007

3. ### Py-FunGuest

On 22 Oct, 13:28, "Diez B. Roggisch" <> wrote:
> Py-Fun 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.

>
> Show us your attempts, and we might suggest a fix. Because otherwise this
> sounds suspiciously like homework.
>
> Diez

Here is my futile attempt. Be careful with this though, I just ran
something similar and it was never ending...

def itforfact(n):
while n<100:
print n
n+1
n = input("Please enter a number below 100")

itforfact(n)

Py-Fun, Oct 22, 2007
4. ### Marco MarianiGuest

Py-Fun 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.

As opposed to what, a complicated one?

Marco Mariani, Oct 22, 2007
5. ### Marco MarianiGuest

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.

Marco Mariani, Oct 22, 2007
6. ### Duncan BoothGuest

Py-Fun <> 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.
>

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

Duncan Booth, Oct 22, 2007
7. ### Py-FunGuest

On 22 Oct, 13:43, Marco Mariani <> wrote:
> 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.

Marco, Thanks for the tip. This now works:

def itforfact(n):
while n<100:
print n
n = n+1
n = input("Please enter a number below 100")

itforfact(n)

Is it a "factorial" though?

Py-Fun, Oct 22, 2007
8. ### Guest

On Oct 22, 2:43 pm, Marco Mariani <> wrote:
> 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.

lambda n: n<=0 or reduce(lambda a,b: long(a)*long(b),xrange(1,n+1))

, Oct 22, 2007
9. ### Amit KhemkaGuest

On 10/22/07, Py-Fun <> wrote:
> On 22 Oct, 13:28, "Diez B. Roggisch" <> wrote:
> > Py-Fun 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.

> >
> > Show us your attempts, and we might suggest a fix. Because otherwise this
> > sounds suspiciously like homework.
> >
> > Diez

>
> Here is my futile attempt. Be careful with this though, I just ran
> something similar and it was never ending...
>
> def itforfact(n):
> while n<100:
> print n
> n+1
> n = input("Please enter a number below 100")
>
> itforfact(n)

Let me give you a pseudo code (which though can be found in most of
the textbooks and some 'simple' googling). Try to understand the code
and then write an equivalent python function.

function iFactorial(n: integer): integer;
var i, temp: integer;
begin
temp = 1;
for i = 1 to n do
temp = temp * i
end
return temp

1. why doesn't it surprise you if the code that you posted goes in
infinite loop ?!
2. why do you use condition: n < 100
3. How do you think that your function will calculate the factorial ?
4. Instead of "input" use "raw_input", and then "cast" the input as integer .

Cheers,
amit.
--
--
Amit Khemka

Amit Khemka, Oct 22, 2007
10. ### vimalGuest

On Oct 22, 5:43 pm, Marco Mariani <> wrote:
> 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

vimal, Oct 22, 2007
11. ### AntGuest

On Oct 22, 1:26 pm, Py-Fun <> 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.

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

Ant, Oct 22, 2007
12. ### Marco MarianiGuest

From the cookbook, this time.
It satisfies the requirements nicely

http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/496691

def tail_recursion(g):
'''
Version of tail_recursion decorator using no stack-frame
inspection.
'''
loc_vars ={"in_loop":False,"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',args, 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

Marco Mariani, Oct 22, 2007
13. ### Tim GoldenGuest

Marco Mariani wrote:
> From the cookbook, this time.
> It satisfies the requirements nicely
>
>
> http://aspn.activestate.com/ASPN/Cookbook/Python/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

Tim Golden, Oct 22, 2007
14. ### Marco MarianiGuest

Tim Golden wrote:

>> From the cookbook, this time.
>> It satisfies the requirements nicely
>>
>> http://aspn.activestate.com/ASPN/Cookbook/Python/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?

Marco Mariani, Oct 22, 2007
15. ### Peter GoodmanGuest

On Oct 22, 8:26 am, Py-Fun <> 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.

def fac_btt(num):
total = 1
if num > 1:
for i in range(1, num+1):
total *= i

Peter Goodman, Oct 22, 2007
16. ### Paul McGuireGuest

On Oct 22, 8:02 am, vimal <> wrote:
> On Oct 22, 5:43 pm, Marco Mariani <> wrote:
>
> > 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

Paul McGuire, Oct 22, 2007
17. ### Michael J. FrombergerGuest

In article <>,
Py-Fun <> 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

Michael J. Fromberger, Oct 22, 2007
18. ### Tim GoldenGuest

Marco Mariani wrote:
> Tim Golden wrote:
>
>>> From the cookbook, this time.
>>> It satisfies the requirements nicely
>>>
>>> http://aspn.activestate.com/ASPN/Cookbook/Python/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

Tim Golden, Oct 22, 2007
19. ### Guest

On Oct 22, 7:50 am, Duncan Booth <> wrote:
> Py-Fun <> 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.

>
> 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, 2007
20. ### Paul RudinGuest

"" <> writes:

> On Oct 22, 7:50 am, Duncan Booth <> wrote:
>> Py-Fun <> 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.

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

Paul Rudin, Oct 22, 2007