Recursion

[Remco Gerlich]

Bob Calco <rcalco at cortechs.com> wrote in comp.lang.python:
> Anyone:
> 
> I noticed the following while dabbling in Perl, Ruby and Python recently.
> Take your standard factorial implementation, a la:
> 
> PYTHON
> ======
> import sys
> 
> def factor(n):
>   if n == 1:
>     return 1
>   else:
>     return n*factor(n-1)
> 
> print factor(int(sys.argv[1]))

(snip)

> The highest value for n you can run in Python is 12; after that you get
> overflow error messages. In Perl, the largest value is 170 (after which you
> get 1.#INF for an answer). In Ruby, you can input a value as high as 763
> before you get a SystemStackError (stack level too deep) error.


I don't have time to answer your other questions, but note that this is a
very naive implementation. For huge numbers, Python provides long integers
that can grow to arbitrary length. '1L' is the long integer 1. So if you
change it to

def factor(n):
   if n==1:
      return 1L
   else:
      return n*factor(n-1)

It works way better. It now works up to 999 before you walk into the builtin
recursion limit. Changing to a simple non-recursive version is still a lot
better:

def factor(N):
   n = 1L
   for i in xrange(1,N+1):
      n *= i
   return n

And now the limit is simply your memory, you need enough to hold all the
digits (and some patience).

Using oversimplified code for benchmarks isn't very useful.

> I'm trying to decide which of these languages to embed in my application or
> at the very least require in the user environment. I like all of them, and I
> lean toward Python because it's much cleaner than Perl and more mature than
> Ruby and Mark Hammond's Win32 extenstion fully supports COM on Win32, which
> would make it a very useful framework for prototyping our COM objects and
> developing our own test suites to exercise them when they are implemented in
> C++. But I was surprised to find such a difference when testing each
> language's support for recursion.

Note that the limit you found had to do with the size of integers mostly,
not with recursion.

I *think* Stackless Python has no recursion limit since it doesn't use the C
stack, but I don't know for sure.

-- 
Remco Gerlich