Recursion

[Tim Peters]

[Bob Calco]
> I noticed the following while dabbling in Perl, Ruby and Python
> recently.  Take your standard factorial implementation, a la:

You'll find that it's a lot faster to use iteration than recursion in these
languages.

> PYTHON
> ======
> import sys
>
> def factor(n):
>   if n == 1:
>     return 1

Change that to

      return 1L

and it will use unbounded ints instead.

>   else:
>     return n*factor(n-1)
>
> print factor(int(sys.argv[1]))
>
> fact.pl
> =======
> sub fact {
>   my($n) = shift;
>   if ($n eq 1) {
>     return 1;
>   } else {
>     return ($n * fact($n-1));
>   }
> }
> print fact($ARGV[0]), "\n";
>
> fact.rb
> =======
> def fact(n)
>   if n == 1
>     1
>   else
>     n*fact(n-1)
>   end
> end
> print fact(ARGV[0].to_i), "\n"
>
> The highest value for n you can run in Python is 12; after that
> you get overflow error messages.

ints, longs (unbounded integers), and floats are distinct types in Python.
The max size of an int depends on the platform, but on most machines it's a
32-bit signed integer (use sys.maxint to see what's true on your platform).
Stick "L" at the end of an int literal to make it an unbounded int instead,
or use the builtin long() function to convert to unbounded int.

> In Perl, the largest value is 170 (after which you get 1.#INF for
> an answer).

All numbers in Perl are cast to C doubles internally (in the absence of some
"use" directive trickery added to Perl5).  Perl doesn't support unbounded
integers natively (if you want them, you need to use a library module).

> In Ruby, you can input a value as high as 763 before you get a
> SystemStackError (stack level too deep) error.

The recursion limit in Python varies across platforms; I assume that's true
in Ruby too; in Python you can use sys.setrecursionlimit() to fiddle it (but
if you set it "too high", you risk having the interpreter blow up due to C
stack corruption).

> Couple questions:
>
> 1. Why the vast difference between the languages?

Why not <wink>?

> Is this apparent limitation in Python deliberate, or the
> consequence of some other design decision?

Python distinguishes between ints (native C "long") and longs (unbounded)
because ints are often used as arguments to C libraries.  If you want
unbounded ints, you have to "do something" to get them.  This distinction
made more sense 10 years ago when it was first made; it's gotten more clumsy
not because of factorials <wink>, but because systems are getting larger,
and systems that support files larger than 2Gb are becoming more common
(i.e., 32-bit signed ints no longer suffice for some common file
operations).  The distinction between ints and longs isn't as sharp as it
used to be:  every release, a few more pieces of the internals tolerate
either.  Over time, I expect the user-visible distinction will mostly
vanish.

> 2. In the real world, does this really matter? Does Ruby have any
> meaningful advantage over Python in this regard? (I understand I
> might get different replies if I asked this question on the Ruby
> email list. I have different questions for Ruby fans!)

If you need unbounded ints, Python and Ruby will both do fine, but Perl is a
distant third in that respect.

> 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.

Except you didn't test recursion:  you inadvertently tested limits on
integer sizes (or, in Perl's case, the overflow limit of IEEE-754 doubles).

most-people-should-never-use-numbers<wink>-ly y'rs  - tim