フィボナッチ数をPerlで実装できますか？

そもそもフィボナッチ数が何なのかまったくわからなかった。くやしいです。
くやしいので勉強してみた。

フィボナッチ数とは

くわしくはwikiを参照

http://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A3%E3%83%9C%E3%83%8A%E3%83%83%E3%83%81%E6%95%B0

コード置き場

ここにコードを置いてあります。
https://github.com/okamuuu/Fibonacci

実装前に準備すること

スケルトン作成

% module-setup Fibonacci                                   
...
% cd Fibonacci

テスト作成。

#!/usr/bin/env perl
use strict;
use warnings;
use Test::More;

BEGIN {
    use_ok('Fibonacci');
};

my $expected = [ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 ];

subtest 'get fibonacci number' => sub {

    my $got = Fibonacci->get_number_at(4);
    is($got, $expected->[4]);
};

done_testing;

実行する。もちろん失敗。

:!prove -vl t/01_fibonacci.t                                               
t/01_fibonacci.t .. 
ok 1 - use Fibonacci;
Can't locate object method "get_number_at" via package "Fibonacci" at t/01_fibonacci.t line 14.
    # Child (get fibonacci number) exited without calling finalize()
not ok 2 - get fibonacci number
...

実装開始

フィボナッチ数の定義はどの項もその前の2つの項の和となっている。という事なのでベタに次のように書いてみる

package Fibonacci;
use strict;
use warnings;
our $VERSION = '0.01';
use Carp ();

sub get_number_at {
    my ($class, $length) = @_;

    if ( $length == 0 ) {
        return 0;
    }

    ### 1つ目、2つ目の数はその2つ前の値が存在しない
    if ( $length == 1 or $length == 2 )  {
        return 1;
    }   

    my @numbers;

    for my $len ( 1 .. $length ) { 
        if ( $len == 1 ) { 
            $numbers[$len] = 1;
        }   
        elsif ( $len == 2 ) { 
            $numbers[$len] = 1;
        }   
        else {
            $numbers[$len] = $numbers[$len-1] + $numbers[$len-2]; 
        }   
    }   

    return $numbers[$length-1] + $numbers[$length-2];
}

1;

テスト実行。成功。

:!prove -vl t/01_fibonacci.t
...
All tests successful.
};

done_testing;

テストケースを増やしてみて再度prove実行。成功。

#!/usr/bin/env perl
use strict;
use warnings;
use Test::More;

BEGIN {
    use_ok('Fibonacci');
};

my $expected = [ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 ];

subtest 'get fibonacci number' => sub {

    my $count = scalar @{ $expected } - 1;
    for my $length ( 0 .. $count ) { 
        my $got = Fibonacci->get_number_at($length);
        is($got, $expected->[$length]);
    }  
};

done_testing;

:!prove -vl t/01_fibonacci.t
...
All tests successful.
Files=1, Tests=2,  0 wallclock secs ( 0.05 usr  0.01 sys +  0.04 cusr  0.00 csys =  0.10 CPU)
Result: PASS

面接官が試したかった事。

Fibonacci.pmのget_number_atメソッドの最後にあるこの記述。再帰の匂いがぷんぷんします。

return $numbers[$length-1] + $numbers[$length-2];

ああなるほど面接官が知りたかったのは「再帰処理を書けるのかい？んん？」とそういうわけですね。承知した。

再帰処理に書き換える

lib/Fibonacci.pmを次のように書き換えます。
うおー。シンプル!!

package Fibonacci;
use strict;
use warnings;
our $VERSION = '0.01';

sub get_number_at {
    my ($class, $length) = @_; 

    if ( $length == 0 ) { 
        return 0; 
    }   

    if ( $length == 1 or $length == 2 ) { 
        return 1;
    }   

    return $class->get_number_at($length-1) + $class->get_number_at($length-2);
}

1;

テスト実行。当然成功。

:!prove -vl t/01_fibonacci.t                                               
t/01_fibonacci.t .. 
..
All tests successful.

感想

再帰処理は見た目何が何やら分からないかも知れませんが、どっかにwarnでも挿入して実行してみると何やってるか良く分かります。
小一時間程度でしたが割といい勉強になりました。おしまい。