[Tutor] factorial

[Danny Yoo]

On Fri, 10 Jan 2003, Magnus Lycka wrote:

> It probably has something to do with 42. Maybe it required
> 1405006117752879898543142606244511569936384000000000 operations for Deep
> Thought to come up with its answer?
>
> Factorial rarely comes up in contexts like this because the result it
> calculates is useful, but rather because it's simple to demonstrate
> recursion with it. I much prefer Fibonacci numbers, but implementing
> Fibonacci with recursion is even more stupid than implementing Factorial
> that way.
>
> Function calls have a cost, as the recent discussion should have
> revealed. The limited amount of stack space is used, and it takes time
> and memory to put context on the stack.


Hi everyone,

As a qualification: function calls have a cost in many languages,
including Python.  However, not all!  There are some programming
languages, particularly the functional languages, where function calls can
come "for free" under certain circumstances.

These circumstances come under the name "tail calls".



> So, if you need factorials in real life (who does?) it's much better to
> do:
>
> def fac(n):
>      prod = 1
>      for i in range(1, n+1):
>          prod *= i
>      return prod
>
> or if you are of the other inclination...
>
> def fac(n):
>      import operator
>      return reduce(operator.mul, range(1,n+1))



There is a way of reformulating this so that it's still written using
recursion, but it's just as efficient as a loop.  For example, here's an
"iterative" version in the Scheme language:

;;;;;;

guile> (define (fact-iter n a)
          (if (= n 0)
              a
              (fact-iter (- n 1) (* n a))))
guile> (define (factorial n)
          (fact-iter n 1))
guile> (factorial 40)
815915283247897734345611269596115894272000000000
guile> (factorial 42)
1405006117752879898543142606244511569936384000000000
;;;;;;


This runs without any stack overhead in Scheme.  There's a section in The
Structure and Interpretation of Computer Programs that explains the idea
of an iterative process using recursion, for those who are interested in
this subject:

    http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2

The link above includes a neat diagram that shows intuitively why certain
processes are forced to take up stack space, and why others may actually
take a constant amount of space.




> Fibonacci numbers are much nicer, because the ratio of two adjacent
> fibonacci numbers get closer and closer to the Golden Ratio the higher
> they get. The Golden Ratio is something really important. You can ask
> any ancient Egyptian, landscape photographer or plastic surgeon about
> that.
>
> But while recursive factorials are only linearly wasteful, the function
> below is much worse. Think about it.
>
>  >>> def fib(n):
> ...     if n <= 1: return 1
> ...     else: return fib(n-2) + fib(n-1)



But fib() is not expensive by necessity: we can reformulate this recursive
definition as an iterative process, even with recursion:

###
def fib(n):
    return fib_helper(n, 1, 1)

def fib_helper(n, x, y):
    if n == 0:
        return x
    return fib_helper(n-1, y, x+y)
###

And in theory, this should run without any cost related to function
calling or stack usage...  But unfortunately, the current implementation
of Python doesn't optimize tail calls, so this runs abysmally in Python.
*sigh*


But it's still a good idea to be aware that function calls themselves
don't have to be expensive by nature.  It's only the current
implementations of Python that places a cost to function calls.  But if
CPython and Jython does ever get tail call optimization, I will be a very
happy person.  *grin*