Recursion

[Bjorn Pettersen]

It's all a question of wheter you use regular integers, or long integers:

>>> def fact(n):
...  if n==1:
...   return 1L
...  else:
...   return n*fact(n-1L)
...
>>> fact(12L)
479001600L
>>> fact(100L)
93326215443944152681699238856266700490715968264381621468592963895217599993229915

608941463976156518286253697920827223758251185210916864000000000000000000000000L
>>> fact(800L)
77105301133538600414463939777502836059555640181601023916341099403397085182709306

93670907697955390330926478612242306774446597851526397454014801846531749097625044

70638274259120173309701702610875092918816846985842150593623718603861642063078834

11723409851372526504540252305657565886062123887041264021962997102468682662471338

36609631270481955722797077116883526202598691409949012878957472904107224961061519

54257267396322405556727354786893725785838732404646243357335918597747405776328924

77589756451958359135408089811702313276225071405727134411094816402994058882784778

04423144732004795251383182083024277278031332193052109525076059489943143454493252

59594876385922128494560437296428386002940601874072732488897504223793518377180605

44178311664970826994606138023053101829193051074866557780301452325179779038861503

37565448303749094401622701829523033290917204382106370971056162583870518840302889

33650309756289188364568672104084185529365727646234588306683493594765274559497543

75965173369982063973170211691296324744129420029780008706172586822388086524358336

56234827043958936527118407354187997737630548875882199439846734010513622803841878

18611005035187862707840912942753454646054674870155072495767509778534059298038364

20407629904807293450104625517537832300821767073164951995569908448233079881104916

62762492513265443125802893578129248258982174628482976483494008388154101528724567

07653654424335818651136964880049831580548028614922852377435001511377656015730959

25464717129093051734036728765700760617767548383052149970787344901684440239020374

66330869697476806714685416872658236379220074138491185934877102728831649055487071

98762911703545119701275432473548172544699118836274377270607420652133092686282081

77738367448788162880080192810301583282102128632212046087494169719948775876973054

49220123896945049600000000000000000000000000000000000000000000000000000000000000

00000000000000000000000000000000000000000000000000000000000000000000000000000000

000000000000000000000000000000000000000000000000000000000L


Bob Calco wrote:

> 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]))
>
> 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. 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.
>
> Couple questions:
>
> 1. Why the vast difference between the languages? Is this apparent
> limitation in Python deliberate, or the consequence of some other design
> decision?
>
> 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!)
>
> 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.
>
> Any thoughts welcome.
>
> Sincerely,
>
> Bob Calco
> CorTechs, Inc.
> rcalco at cortechs.com