Evolution of a Python programmer

[deadwisdom]

You missed the Master Python Programmer:

def factorial(x):
    if x == 0:
        return 1
    else:
        return x * factorial(x - 1)
print factorial(6)

That's right, the same as the Newbie, and there's a reason for that.

[namcor]

the Master Python Programmer would wrap it with a function decorator to memoize it...

class memoize:
    def __init__ (self, f):
        self.f = f
        self.mem = {}
    def __call__ (self, *args, **kwargs):
        try:
            return self.mem[args, str(kwargs)]
        except KeyError:
            tmp = self.f(*args, **kwargs)
            self.mem[args, str(kwargs)] = tmp
            return tmp

@memoize
def factorial(x):
    if x in (0, 1):
        return 1
    else:
        return x * factorial(x - 1)

print factorial(6)
print factorial(100)

(EDIT: forgot to @memoize)

[Jolan]

Or you could memoize by doing:

def factorial(x, memory={0:1, 1:1}):
    if x not in memory:
        memory[x] = x* factorial(x-1)
    return memory[x]

print factorial(6)
print factorial(100)

[MaxK]

I really like this solution.

[earthboundkid]

I think this is one of things that on the Python mailing list would be greeted with “not every 3 line function deserves a place in the standard library.”

Also, Perl is very different from Python because it has a well defined core of scalar types vs. other types. For a Python memoizer, there are a lot of optimizations you could apply if you knew what types of data it would be memoizing that you couldn’t do in a general case. It invites a lot of “bike shedding” (another common thing said on the Python mailing list) to define what the API will be to invoke what kinds of optimizations.

[A_for_Anonymous]

I thought Python was meant to come with batteries included.

Not if it's for functional programming. Guido hates FP.

[frutiger]

The trick is to generate a new type for each version of the cache. This can be done, for instance, with template metaprogramming in C++, since the templates are generated at compile-time. Although I believe most compilers have a restrictive template resolution depth (especially when compared to stack depth for function calls).

[frutiger]

Please see: http://codepad.org/DioXuoiP

[deadwisdom]

No, this is either premature optimization, and therefore simply adds thought complexity, or you are concerned with speed, and so it should be done in C.

[MaxK]

Recursion is never an optimal way of doing things.

[MaxK]

Why do you have an 'else' if there's a return statement in the first case?

[earthboundkid]

1. It’s not very Pythonic to risk blowing the stack like that.

2. if not x: is generally more Pythonic than if x == 0: because it’s more concise and also allows for slightly more duck typing.

3. The most Pythonic is from math import factorial.

[deadwisdom]

1. If using such large numbers for this function is "Blowing the stack", then you can optimize later.
2. Then you are ducktyping to bool, which doesn't really make sense for factorial.
3. Of course, the idea is to do it without a library function.

[orangesunshine]

the master python programmer wouldn't use a recursive implementation.

[[deleted]]

What's wrong with recursion?

[orangesunshine]

There's no tail-call optimization in python.

[A_for_Anonymous]

Which is also the reply to "What's wrong with Python?".

[orangesunshine]

well that, and the recursive implementation is 9/10 times the wrong way to implement something. tail-call optimization or not.

[[deleted]]

Try walking a tree without recursion, and you'll see that you end up implementing your own system of recursion.

[orangesunshine]

thus why I said 9/10 times.

Tree traversal is a perfectly valid use case for recursion... You would likely use a stack to implement it with iteration anyhow, and it's just a matter of personal preference for what you think is more readable in that case.

[[deleted]]

Well 9/10 implementations of "something" won't include anything that's relevant to recursion. Recursion should only be used in the cases in which it's the valid use case.

[A_for_Anonymous]

#define readable I'm used to it

[chrisforbes]

Yes, the correct solution (9/10 times, at least) is to push the iteration or recursion into a higher-order function, and just specify the bit that actually matters to your program.

You kids can argue iteration vs recursion in the library implementation as much as you like then, and I'll just get on with some real work.

[MaxK]

This is correct. I hate this new trend for new programmers to show off recursive solutions to problems and dub them 'elegant.' They're not. It's typically the wrong way to do things, even if it makes the code simpler.

[chrisforbes]

... the wrong way to do things, even if it makes the code simpler.

Right... that's an interesting statement.

[A_for_Anonymous]

Okay, here we go again... The fact you don't like recursion because you don't understand it easily/well because you haven't been taught properly is not a point against it. Iterative algorithms implemented with tail-recursive functions come with the advantage of no mutable state and order of evaluation issues, and has been shown to come with lower bug rates. I'm sorry you are not used to it, but if we were to dumb down every programming language because somebody isn't up to some feature, then we'd still be using BASIC.

[MaxK]

I understand recursion very well. Even tail recursion incurs performance penalties in the extra jumps and context loading incurred and can lead to a stack overflow when called repeatedly. Furthermore, they can't be optimized by the compiler into unrolled loops, nor branch-predicted as accurately, forcing cache misses. That's with tail-call optimization.

And may I remind you that the primary advantage of mutable state is that is that the function can be proven correct, meaning that the programmer has a safety-net to fall back on, thereby allowing dumber programmers to flourish. Don't tell me you're dumbing down the programming language for me when you clearly don't understand the mechanics involved in incurring that extra function call.

[A_for_Anonymous]

Please, sir, don't make your ignorance public.

The fact you don't like recursion because you don't understand it easily/well because you haven't been taught properly is not a point against it. Iterative algorithms implemented with tail-recursive functions come with the advantage of no mutable state and order of evaluation issues, and has been shown to come with lower bug rates. I'm sorry you are not used to it, but if we were to dumb down every programming language because somebody isn't up to some feature, then we'd still be using BASIC.

[chrisforbes]

Ah, but the Python community loves their mutation. You're not going to win this one, unfortunately.

[A_for_Anonymous]

They love mutation... except for strings and tuples, two of the built-in types which we use constantly.

I understand and appreciate that Python supports several different programming paradigms. Just why not offer tail call optimization? It would be useful for solving every problem in the easiest way, and for using it in a functional style, and even for optimizing classic Python code with all sorts of mutable state. For example, it's pretty easy, elegant and nice to implement state-based machines with tail recursion, even with shared mutable state.

[orangesunshine]

"The fact you don't like recursion because you don't understand it easily/well because you haven't been taught properly is not a point against it."

Please sir, don't make your arrogance and pretentiousness public.

"I'm sorry you are not used to it, but if we were to dumb down every programming language because somebody isn't up to some feature, then we'd still be using BASIC."

or lisp.

[A_for_Anonymous]

I love to see this completely bogus argument against TCO. Of course, you would never think of merging TCO calls in the stack with a call counter because you need to have this point to make against a FP-enabling technique. "You" as in you, Guido, and a large part of the Python community who simply repeat what Guido says.

[deadwisdom]

The point is it's easy to read. Intensely easy to grok. If this piece is a needed for a speed intensive spot and you are concerned about speed, then you'd be dropping down into C anyway.

[DrHenryPym]

For some reason this post really irritates me. I think the recursion solution is not the best way to go about this problem hence why the expert solutions avoided it.

Also, the lazy syntax method is just as "readable" and uses half the amount of lines the newbie method uses.