Higher order perl 1_2

Higer order perl 1_2は階乗に関するお話。
factorialで再帰の例題でよく使われる例ですね。

人によるとこんなに再帰で使うべきでないから逆に
教えるなといいますよね。でもまあ勉強なんで。

比較のコードを書いてみた。

#!/usr/bin/env perl
use strict;
use warnings;

use Benchmark qw(cmpthese);

my $do_test = shift @ARGV;

if (defined $do_test) {
    use Test::More;

    is(factorial(1), 1);
    is(factorial(2), 2);
    is(factorial(5), 120);
    is(factorial(7), 5040);

    is(factorial_tail_recursive(1), 1);
    is(factorial_tail_recursive(2), 2);
    is(factorial_tail_recursive(5), 120);
    is(factorial_tail_recursive(7), 5040);

    is(factorial_loop(1), 1);
    is(factorial_loop(2), 2);
    is(factorial_loop(5), 120);
    is(factorial_loop(7), 5040);

    done_testing();
    exit;
}

cmpthese(500000, {
    normal => sub {
        factorial( 10 );
    },

    tail_recursive => sub {
        factorial_tail_recursive( 10 );
    },

    loop => sub {
        factorial_loop( 10 );
    },
});

sub factorial {
    my $n = shift;

    if ($n == 1) {
        return 1;
    } else {
        return $n * factorial($n - 1);
    }
}

sub factorial_tail_recursive {
    my $n = shift;

    return _factorial_tail_recursive($n, 1);
}

sub _factorial_tail_recursive {
    my ($n, $acc) = @_;

    if ($n == 1) {
        return $acc;
    } else {
        return _factorial_tail_recursive($n - 1, $acc * $n);
    }
}

sub factorial_loop {
    my $n = shift;

    my $val = 1;
    foreach my $num (1..$n) {
        $val *= $num;
    }

    return $val;
}

結果は以下のような具合でした。

                   Rate tail_recursive         normal           loop
tail_recursive 152905/s             --            -8%           -67%
normal         165563/s             8%             --           -64%
loop           458716/s           200%           177%             --

引数を int(rand(10))としたらなぜかうまくいきませんでした。

loopがやっぱり一番早い。あと tail_recursiveの方が遅くなって
しまいましたね。これぐらいの規模の問題だとそんなもんなんかな〜？

この手の問題はループ使って書けってことですかね。