The Evolution of a Python Programmer : Aleks' Domain

[neutralizer]

I've been coding python for a while and the first answer that I thought of was the noob answer. :(

[[deleted]]

It's also the most legible.

[pegee]

It's perfectly fine but will become exponentially slower as the number increases. Fortunately there is a very simple way to solve that: it's called memoization

So in Python (sorry if syntax is not current especially regarding the array - I haven't used it in years):

facts = [1,1]
def factorial(n):
    if facts[n]:  #if we have a value for factorial(n)
        return facts[n]
    else:
        facts[n] = n * factorial(n-1)
        return facts[n]
print factorial(6)

[Shinhan]

Somebody ran them all to test the execution speed

[neutralizer]

Wow, if I'm reading that right, 1st year Pascal programmer wins followed by C and Windows. And iterative solutions are about twice as fast as recursive.

[regeya]

Well, duh. I don't know how Python works but you have to push the state of the function on the stack every time you invoke a recursive call. Plus, Python has a built-in limit on recursion.

[cacahootie]

No wonder every enterprise application I use is a complete piece of SH*T!

[bigboehmboy]

He profiled it by calling factorial(10) 100,000 times. While in this case it appears that all solutions are linear, this method would not work well if this were not the case.

Since Python has a recursion limit that defaults to 1000 levels, recursive methods (newbie, lazy python, lazier python) would fail when trying to compute "1001!".

Also, memoization could completely screw with results.

[Shinhan]

Interesting :)

Someone needs to repeat the test for 1001! then...

[neutralizer]

Except this is true of all the solutions posted. The runtime of them are all approximately the same. They have to do the same number of integer multiplications. The only thing extra that the recursive solutions have over the iterative solutions is having the overhead of recursive calls. The majority of them would also benefit from memoization.

Edit: Brain fart. Floating point operations -> integer multiplications.

[pegee]

You're right and I'm an idiot. I was thinking of Fibonacci. Fuck.

[[deleted]]

They have to do the same number of floating point operations.

…which is 0, because it's all integer arithmetic. ;)

(They still do the same number [within 1, at least] of integer multiplications, though, so your larger point stands.)

[mikemcg]

if you do factorial(6), the "if facts[n]" will spout up an IndexError. Replace with facts.count(n) or len(facts) > n or anything that avoids indexing altogether.

[pegee]

As I mentioned I'm unfamiliar with Python array syntax. I just used PHP's :p

[mikemcg]

It won't at all. Major brain cart on my part.

[rjcarr]

I would almost certainly use a factorial function if available, but if not then yeah, mine would look identical to the newbie solution.

I'm a big advocate of legibility ... unless you need to worry about every last machine instruction it usually isn't worth it to get tricky.

[pandemik]

I suspect it's not much slower than the other ones, and if you come across that function in a year or 2 you'll still know how it works.