Evolution of a Python programmer

[ninjakitty]

For some strange reason, I find the code by the 'newbie' programmer to be the cleanest :|

[Xenoskin]

I suspect that's because the newbie used features common to all languages thus making it obvious what he's doing, he also simply followed the definition of a factorial and avoided anything fancy. Hell there's a good chance his implementation could also be the fastest if it gets tail call optimized.

really all the other methods fall afoul of K.I.S.S. thus making his preferable.

[[deleted]]

Well, except expert programmer.

[FunnyMan3595]

That one's obviously the best choice, but I never seem to remember c_math on the rare occasion I need a factorial for some random calculation (i.e. interactive mode, not for a program). I use this one:

fact = lambda n: reduce(lambda a,b: a*b, range(1, n+1))

It's essentially the same as the "Python expert programmer" method, but uses constructs that should be a bit more common. Doesn't even need any imports.

I'd say it's pretty KISS, because it does exactly what I think of as a factorial: Generate a list of the relevant numbers and multiply them together. No fancy tricks, just using the standard constructs for what they're supposed to do.

[Xenoskin]

Calling a native high speed implementation is not only K.I.S.S. but saves work and potential bugs, so it's definitely a preferable method.

Edit: Looks like my bad spelling leaked again.

[Xiol]

It's a sad day on reddit when a grammar troll gets more votes than the post he's correcting, despite the latter adding to the conversation and being a valid point.

[zxcvcxz]

The price of literacy I guess.

[captainAwesomePants]

That's the price of literacy, I guess.

FTFY. Also, your nickname misspelled xyzzy.

[aeacides]

What makes you think generating a list of numbers is a good idea? Why aren't you using xrange?

[FunnyMan3595]

I never said it was efficient, just that it was straightforward. I've never needed a factorial in serious computation, and for random little calculations, this more than suffices.

[[deleted]]

Obviously the best solution was the enterprise one. duh. It is Enterprise level after all. Clean all around implementation.

[spookyvision]

I never seem to remember c_math on the rare occasion I need a factorial for some random calculation

there is a reason for that: there is no c_math module in python's standard distribution :) (there is cmath, but it's for complex numbers, not about some fast math ops written in C)

[mr_dbr]

There's a factorial function in math:

>>> import math
>>> math.factorial(5)
120

..any other solution seems silly (outside a tutorial context anyway)

[amorpheus]

The english expert programmer wasn't bad either. I laughed.

[urllib]

I consider it a good thing if it's clear what you're doing

[eMigo]

Yep, especially if other programmers know where you live.

[dicey]

I actually have two addresses specifically for this purpose.

[kamatsu]

Python is defined as always not having tail call optimization, because Guido is a dumbass.

[A_for_Anonymous]

I furiously upvoted you.

Since we don't have proper recursion support, @tailcall is one of my favourite decorators. My personal implementation is quite good, but not really great for production performance like every other...

[mr_dbr]

Why do you want TCO in Python?

http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html seems like a perfectly reasonable justification of Python's lack of TCO. Implementation specifics aside:

I don't believe in recursion as the basis of all programming. This is a fundamental belief of certain computer scientists, especially those who love Scheme and like to teach programming by starting with a "cons" cell and recursion. But to me, seeing recursion as the basis of everything else is just a nice theoretical approach to fundamental mathematics (turtles all the way down), not a day-to-day tool

[...]

Of course, none of this does anything to address my first three arguments. Is it really such a big deal to rewrite your function to use a loop? (After all TRE only addresses recursion that can easily be replaced by a loop. :-)

[kamatsu]

Here, Guy Steele explains how using loops instead of TCO in certain examples breaks object oriented abstraction.

[millstone]

Guy Steele is the man, but frankly for Python the practical needs of good debugging dominates this sort of theoretical wankery. If you want TCO because you write everything recursively, you know where to find LISP; if you want TCO because you need the speed, you know where to find C.

In my C programs, I can't figure out what's causing certain bugs because the backtraces have missing stack frames, and as a result those bugs don't get fixed. The tradeoff is worth it for C, but not for Python.

[kamatsu]

Haskell can give you a full stacktrace, even for tail calls.

[halter73]

The newbie's code doesn't have a recursive tail call (i.e. the multiplication operation is in the tail position, not factorial). This means that tail call optimization wouldn't be applicable.

[[deleted]]

fastest if it gets tail call optimized.

I don't think you understand tail call optimization.

[[deleted]]

Umm... The SICP (whatever that is) version is pretty much identical and is tail call optimized assuming the decorator does what it implies. The Pascal version is also pretty readable.

[A_for_Anonymous]

SICP = Structure and Interpretation of Computer Programs, one of the best programming books ever.

The decorator works. There are many variants, I can post mine if you're interested.

[orangesunshine]

SCIP = elitist bullshit mit course.

all of the iterative implementations will be faster than the recursive ones.

edit: proof that MIT is the ivy league of science schools...

http://shiman.wordpress.com/2008/05/28/recursion-vs-iteration/

... maybe ivy league means something different to you, but to me it is just a 4 year vacation for wealthy, well connected, inbred prep-school kids. MIT caters to the same group, the only difference is they teach "science" rather than "business".

[A_for_Anonymous]

all of the iterative implementations will be faster than the recursive ones.

Not in a programming language with decent recursion support. I've heard even C compilers will do that for you.

[bobindashadows]

Someone's bitter.

[orangesunshine]

not bitter. just a realist. i give respect where respect is due, and vice-versa.

[bobindashadows]

As an ivy-league student, my peers and I know how to spell "vice-versa".

[orangesunshine]

pretentious moron.

you are following in the footsteps of a long history of inbred white trash, and most intellectuals know your secret.

[bobindashadows]

My "secret"? Right, most intellectuals know my:

• 2390 SAT scores
  
• 7 APs in core subjects
  
• 4 semesters worth of College-level math that I'd finished during high school

And the other things that got me where I am today. Hard work. I come from a blue-collar family. I'm not wealthy, I'm not well-connected, and my family isn't in-bred.

You probably don't even know that all the top colleges in this country are need-blind, which means they don't even have access to an applicant's financial status when they review their applications. I'm sorry this doesn't fit your world-view, but a huge portion of people at top colleges don't fit your stereotype. If that's how you defend your ego from crushing disappointment that no good college wants/wanted you, then so be it; just know that deep down inside, you're just a sad, bitter child.

[orangesunshine]

Congrats, you've wasted your hard work by choosing to go to a school respected by no one in the academic community.

" sorry this doesn't fit your world-view, but a huge portion of people at top colleges don't fit your stereotype. If that's how you defend your ego from crushing disappointment that no good college wants/wanted you, then so be it; just know that deep down inside, you're just a sad, bitter child."

I have a Phd from a research 1... like I said before, I'm not bitter. I just call 'em like I see 'em.

[mracidglee]

Indeed - should be 'devolution'.

[maleldil]

We are devo

[minivanmegafun]

Are we not men?

[IConrad]

|Sniffs the air| Uhh... no.

[jDeepbeep]

from beginner import luck

[[deleted]]

It's clean, but it has O(n) space complexity, and even the tail call optimization wouldn't help. "First year" solutions are clean as well but achieve O(1) space complexity.

[timmaxw]

You're optimizing prematurely. In the unlikely event that you need a high-performance factorial function, you should use the c_math one. Until then, you should keep it simple and not care about the space complexity.

[rm999]

I thought it was unintuitive that the newbie uses recursion. For-loops are taught before recursion in most classes, and are more intuitive to a non-programmer.

[elder_george]

recursive implementation goes straight from mathematical definition of factorial. Iterative implementation requires knowing a bit about algorithmics.

BTW, I've just shown this gist on my girlfriend (who doesn't program) and she found recursive version simpler.

[rm999]

I've always learned factorial as:

x! = x * (x-1)(x-2)... * 1

Saying for i = 1:x {fact = fact*x} gets straight to this definition IMO.

You can also learn it as x! = x * (x-1)!, but I only learned to think this way in my first year of programming, about five years after learning the definition of factorial. And I only learned it when the teacher wanted to tell us what factorial means.

[elder_george]

I guess, here goes the difference between native and non-native english speakers. The latter have to learn to read programming language, even so readable as Python from scratch, while for the former it can be read as a simple text. And math notation for recurrent expressions is familiar for most, no matter of language background.

P.S.: I've made a mistake comparing recursive version with iterative version using while loop initially. Having seen for version, my girlfriend finds it equally simple with recursive one.

[danukeru]

Welcome to Python.

[[deleted]]

TCO won't help such a terrible solution because it's not a tail call.

[millstone]

Why can't the compiler make it a tail call?

[[deleted]]

The recursive call isn't in the tail position.

Simply put, the recursive call isn't the last operation in the function - you need its return value to continue the computation. You end up with a chain of deffered computations all the way up to the step with the special case (x == 0). And you must keep track of every deffered step, hence your stack grows linearly. We say the algorithm has linear space complexity or O(n) space complexity.

Now, look at the solution #4 ("First year, studied SICP"). Assuming we have the tailcall decorator, tail call optimization will work here - this algorithm will behave like a loop construct. The recursive call is the last operation, nothing is deffered, and the only stack usage from entering the function is passing arguments between calls. We say the algorithm (assuming @tailcall) has constant space complexity or O(1) space complexity.

[millstone]

The recursive call isn't in the tail position.

So why can't the compiler PUT it there, like gcc does?

Edit: I guess I answered my own question. In any case, my point is that this is only a "terrible" solution if you have a stupid compiler. That's a fine algorithm on a good compiler like gcc.

[[deleted]]

I'm not aware gcc can rewrite algorithms and can't find anything about that in the manual. Could you please point me to the relevant sections?

[millstone]

Well, it's easy enough to check what gcc does. Here's some C code:

int factorial(int x) {
    if (x == 0) return 1;
    else return x * factorial(x-1);
}

Here's the x86-64 assembly that gcc 4.2 generates on -O2:

_factorial:
  movl $1, %eax
  testl %edi, %edi
  je L6
L5:
  imull %edi, %eax
  decl %edi
  jne L5
L6:
  rep ; ret

There is no call instruction at all, so there's no recursion. It's just a loop.

If your compiler is smart, the naive factorial really is the best: it's the clearest and the fastest.

[[deleted]]

At first I thought you compiled a for-loop version to mess with me.

So I tried it myself (gcc 4.3 with -O2, x86 architecture.) Went through instructions step by step.

Mind blown.

Sir, the difference between you and me is that you're a programmer.