再帰呼び出しに関しての暇つぶし実験

いくつかの言語で、無限再帰呼び出しを行うプログラムを書いてみて、何回呼び出せるかを調べてみた。

実験環境は、特筆がなければ次の通り:

CPU: Intel Core2Quad Q6600
Mem: DDR2 SDRAM 4096MB
O S: Linux 2.6.18 (CentOS 5.2) x86

Bash

実験コードは次の通り。

#!/bin/bash

ctr=0

function func {
    ctr=`expr $ctr + 1`
    echo "${ctr} th function call."
    func
}

func

結果は、

12267 th function call.
12268 th function call.
 th function call.
 th function call.
セグメンテーション違反です

こうなった。なお、何度か実行すると数回程度の誤差が生じるようだ。

なお、bashのバージョンは

$ bash --version
GNU bash, version 3.2.25(1)-release (i686-redhat-linux-gnu)
Copyright (C) 2005 Free Software Foundation, Inc.

C言語

実験コードは次の通り。

#include<stdio.h>

int testval;

void testfunc(void)
{
  testval++;
  printf("%d th function call.\n",testval);
  testfunc();
}

int main(void)
{
  testval=0;
  testfunc();
}

結果は、

785545 th function call.
785546 th function call.
セグメンテーション違反です

こちらもばらつきアリ。
なお、コンパイラは

$ gcc --version
gcc (GCC) 4.1.2 20071124 (Red Hat 4.1.2-42)
Copyright (C) 2006 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Ruby

実験コードは次の通り。

$ctr=0

def testfunc
  $ctr += 1
  puts "#{$ctr}th function call."
  testfunc
end

testfunc

結果は、

5469th function call.
5470th function call.
./stack.rb:5:in `puts': stack level too deep (SystemStackError)
        from ./stack.rb:5:in `testfunc'
        from ./stack.rb:6:in `testfunc'
        from ./stack.rb:9

こちらは5470回から変わらず。

なお、rubyのバージョンは:

$ ruby --version
ruby 1.8.5 (2006-08-25) [i386-linux]

PHP

実験コードは次の通り。

<?PHP
$ctr=0;

function func(){
  global $ctr;
  $ctr++;
  print $ctr . "th function call.\n";
  func();
}

func();

?>

結果は、

31389th function call.
31390th function call.
セグメンテーション違反です

こちらもばらつきアリ。

なお、phpのバージョンは:

$ php --version
PHP 5.1.6 (cli) (built: Jul 16 2008 19:53:00)
Copyright (c) 1997-2006 The PHP Group
Zend Engine v2.1.0, Copyright (c) 1998-2006 Zend Technologies

Perl

実験コードは次の通り。

$ctr=0;

sub func {
  $ctr++;
  print $ctr . "th function call.\n";
  func();
}

func();

結果は、

5657634th function call.
5657635th function call.
Out of memory!

こちらは安定的な結果に。

なお、perlのバージョンは:

$ perl --version

This is perl, v5.8.8 built for i386-linux-thread-multi

Copyright 1987-2006, Larry Wall

C#

実験環境は、同じ構成でWindows XP Professional SP3。
実験コードは次の通り。

using System;

namespace fstack
{
    class Program
    {
        static int ctr = 0;

        static void Main(string[] args)
        {
            testfunc();
        }

        static void testfunc()
        {
            ctr++;
            Console.WriteLine(ctr.ToString() + "th function call.");
            testfunc();
        }
    }
}

結果は、

59834th function call.
59835th function call.
↑ここでSystem.StackOverflowExceptionが発生。

こちらも安定的な結果となった。

なお、VisualStudio 2008 Professionalを使用。Releaseバイナリで実行した。

結果

言語	呼び出し回数(概数)
Perl	5,657,634
C言語	785,545
C#	59,834
PHP	31,389
Bash	12,267
Ruby	5,469

まさかのPerl。高級言語になればなるほど呼び出し回数は少なくなるイメージはありましたが、C#>PHPはちょっと意外。

なお、研究室のAたまおかC人たちが関数型言語で挑戦してくれていますが、どうやら終わる気配がないようです。というわけで今日はここまで。結果が出たら追記します。