2012年2月28日火曜日

再帰について

順列問題を解く

CodeEval より
【問題】
Write a program to print out all the permutations of a string in alphabetical order.

例えば、
hat
という入力に対しては、

aht,ath,hat,hta,tah,tha
と出力する。

順列のような問題は、なんとなく再帰を使うのが良いような気がする。
#! /usr/bin/perl

use strict;
use warnings;

sub perm{
    my @orig_arr = @_;

    if ( scalar(@orig_arr) <= 1 ){
        my $result = shift @orig_arr;
    }
    else {
        my @result = ();
        for (0..scalar( @orig_arr )-1){
            my @workarr = @orig_arr;
            my $top_char = splice( @workarr, $_, 1);

            push @result, map { $top_char.$_ } perm( @workarr );
        }
        @result;
    }
}

sub solve{
    my @result = sort ( perm(split //, shift) );
    foreach (@result){  
        print $_.", ";
    }
    print "\n";
}

solve("hat");

ループでも解けるでしょうか?
再帰でできることは for 文(ループ)でもできるはずなのですが、今回の場合は for 文は意外と難しそう。
何が難しいのかというと "hat" のように 3 文字で固定であれば 2 つの for 文のネストでできますが、 文字数は可変なので静的なプログラムが書けない(と思う)。 for 文を結局再帰したくなる・・・。
そこで、新しい発見かもしれない教訓、

”繰り返し数が固定でない場合は、再帰処理が有効”


再帰は危険

for 文で書くのに何かヒントは無いかと、Code Complete を紐解いてみる。 「再帰を使って行えることは全て、スタックと繰り返しを使って行うことができる」とある。
そうかスタックね。・・・でもわからん。この問題はしばらく寝かせよう・・・。

ところで、前述の本には「再帰の使用に関するヒント」という項目に有用なヒントが幾つかあって、最後に「階乗やフィボナッチ数列に再帰を使用しない」とある。
そして、再帰は遅くて、消費メモリの予測ができなくて、理解が難しいと説明してあり、さらにかなり強い調子で「仮に、私の部下が再帰を使って階乗を計算しようものなら、別の誰かを雇うだろう」といっている。
上司によっては職を失いかねない危険をはらんでいます。再帰を使うときは要注意っと。






0 件のコメント:

コメントを投稿