Iteration for Factorials

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

  1. Py-Fun

    Py-Fun Guest

    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
    #1
    1. Advertising

  2. 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
    #2
    1. Advertising

  3. Py-Fun

    Py-Fun Guest

    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
    #3
  4. 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
    #4
  5. 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
    #5
  6. Py-Fun

    Duncan Booth Guest

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

    Py-Fun Guest

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

    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
    #8
  9. Py-Fun

    Amit Khemka Guest

    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

    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.
    --
    --
    Amit Khemka
     
    Amit Khemka, Oct 22, 2007
    #9
  10. Py-Fun

    vimal Guest

    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
    #10
  11. Py-Fun

    Ant Guest

    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
    #11
  12. 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
    #12
  13. Py-Fun

    Tim Golden Guest

    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
    #13
  14. 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
    #14
  15. 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
    return total
     
    Peter Goodman, Oct 22, 2007
    #15
  16. Py-Fun

    Paul McGuire Guest

    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
    #16
  17. 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
    #17
  18. Py-Fun

    Tim Golden Guest

    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
    #18
  19. Py-Fun

    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
    #19
  20. Py-Fun

    Paul Rudin Guest

    "" <> 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
    #20
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Phil Weldon

    Re: Factorials

    Phil Weldon, Sep 20, 2003, in forum: Python
    Replies:
    10
    Views:
    637
    Jacek Generowicz
    Sep 23, 2003
  2. waldo

    factorials in C

    waldo, Oct 18, 2011, in forum: C Programming
    Replies:
    0
    Views:
    343
    waldo
    Oct 18, 2011
  3. waldo

    factorials and recursion

    waldo, Oct 18, 2011, in forum: C Programming
    Replies:
    0
    Views:
    250
    waldo
    Oct 18, 2011
  4. Thufir
    Replies:
    11
    Views:
    237
    Todd Benson
    Nov 8, 2007
  5. Adam Trager

    Factorials

    Adam Trager, Jul 14, 2008, in forum: Ruby
    Replies:
    5
    Views:
    198
    Serabe
    Jul 14, 2008
Loading...

Share This Page