gistfile1.pl

use strict;

# 前提
# hanoi(1) -> 1
# hanoi(n) = hanoi(n - 1) + hanoi(n - 1) + 1;

# ということは

sub hanoi { # 関数hanoiを定義
    my $n = shift; # 引数 は "n"

    if ($n == 1) { # 引数が1 の場合は 1 です
        return 1;  # なので1を返します
    }

    # それ以外の場合はhanoi(n - 1)の答えが必要なので
    # 自分を「再帰的」に呼び出しますが、引数は明示的にn - 1にします
    my $n_1 = hanoi( $n - 1 );

    # なので、hanoi(n - 1)が得られたので答えを返します
    return $n_1 + $n_1 + 1;
}

# という、上記のhanoi()関数をここで1から30まで実行します
foreach my $i ( 1 .. 30 ) {
    printf "hanoi(%2d) = %d\n", $i, hanoi($i);
}


# ちなみに 2**$n - 1 でも求められるよ、って事

foreach my $i ( 1 .. 30 ) {
    printf "(2**%2d) - 1 = %d\n", $i, (2 ** $i) - 1;
}