Iteration for Factorials

P

Py-Fun

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.
 
D

Diez B. Roggisch

Py-Fun said:
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
 
P

Py-Fun

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

Marco Mariani

Py-Fun said:
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?
 
M

Marco Mariani

Py-Fun said:
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.
 
D

Duncan Booth

Py-Fun said:
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
 
P

Py-Fun

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?
 
C

cokofreedom

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

Amit Khemka

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

About your code.
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.
 
V

vimal

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
 
A

Ant

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

Marco Mariani

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
 
M

Marco Mariani

Tim said:
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?
 
P

Peter Goodman

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
return total
 
P

Paul McGuire

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
 
M

Michael J. Fromberger

Py-Fun said:
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
 
T

Tim Golden

Marco said:
Tim said:
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 :)
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
 
M

mensanator

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:
mpz(3628800)
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,904
Latest member
HealthyVisionsCBDPrice

Latest Threads

Top