The Recurse of Factorial

I am knowingly going to take a bit of a heterodox view here, but in my opinion, this is actually the most functional of the solutions proposed:

    def factorial(n):
        return prod(range(1, n + 1))

I think the essence of modern functional programming is not recursion per se, but the factoring out (no pun intended in this context) of recursion schemes and making them first-class citizens. Granted, to understand what is going on you need to understand the basics of recursion, so I'm not saying to skip that per se, but I don't think recursion should any longer be taught as the "distinctive characteristic" of this sort of modern functional programming. What's interesting is the factoring out of recursion schemes, the composition of recursion schemes with other recursion schemes (i.e., putting a filter on a map, as the simplest case), and the composition of recursion schemes with other functional tools.

In practice, when programming in Haskell, you recurse a lot less than non-Haskell programmers may have the impression that you do, because you more often use these defined recursion schemes. Recursion is still used, certainly, but even then it's often as some one-off scheme that may be extracted later, or simply as a somewhat hacky way of tricking the compiler to do certain optimizations with no reference to "good code" at all. You can get a long way in Haskell without writing explicit recursion yourself.

I found this sufficiently uninformative that I went back to http://www.willamette.edu/~fruehr/haskell/evolution.html.

Incidentally, if your language has big integer arithmetic (like Python does), the following is substantially faster than the usual iterative or recursive approaches:

    def multiply_range(n, m):
        if m < n:
            return 1
        elif n == m:
            return n
        else:
            mid = (n+m) // 2
            return multiply_range(n, mid) * multiply_range(mid+1, m)

    def factorial (n):
        return multiply_range(1, n)

Try factorial(100000) to see the performance difference. Why this makes a difference is left as an exercise for the reader. (Note, in some languages, like Ruby, converting to a string representation may be the biggest bottleneck.)

A excessively long prose on recursive factorial functions, and the author does not even give one example of a proper tail-recursive implementation?

I’m not familiar with Erlang, but unless it has some really funky syntactic sugar, the Erlang examples aren’t tail-recursive. In all three, the continuation of the recursive call is the multiplication operation and not the conditional.

Is anyone else bothered that there's no bounds checking in any of the implementations? factorial(-1) would likely crash all of them.

The gamma function is part of the posix specification.

I suppose in an interview situation it might be advantageous to compare stirling & lanczos methods.

you're expected to know what -1 factorial is as well.