二つの全く仕上げ（ハノイの塔）

Question

と呼ばれていない再帰私はハノイの問題のタワーのハスケルでこの機能をプログラムします。この機能は、1つの代替スティックでソーススティックから複数のスティックへのステップ数を与えます。

numStepsHanoi :: Integer -> Integer 
numStepsHanoi 0 = 0 
numStepsHanoi n = numStepsHanoi (n-1) + numStepsHanoi (n-1) + 1 

この機能が正常に動作します... Nまで、ディスクの数が、高すぎます。 GHCiは終了しません。私はこの問題の複雑さを知っており、より速く走ることができないことを知っています。例えば

私はn = 64とそれを呼び出す場合、私は20分待ってから（それが完了していない）何も出力を得ることはできません。 n = 20でも約2秒かかります。

別の実装（下記）では、時間がかなり短縮されます。

numStepsHanoi :: Integer -> Integer 
numStepsHanoi 0 = 0 
numStepsHanoi n = 2 * numStepsHanoi (n-1) - 1 

n = 64となり、すぐに結果が得られます。明らかにこれには再帰呼び出しが1つしかありませんが、そのような大きな効果がありますか？

これはGHCi最適化の問題でしょうか？

Answer 1

私は、これは実際にが機能の複雑である疑いがあります。あなたの最初のバージョンはすべての呼び出しに対して2つの再帰呼び出しを行います。複雑さはO（2^n）です。 n = 64の場合、合計で2つの通話を行います。それはおおよそ37×10^18のコールです。したがって、現在のコンピューティングパワーでこの生涯の結果を見るつもりはありません。 1マイクロ秒当たりの1コールでも、それはまだ1000万年をはるかに超えています。

2番目のルーチンは、繰り返しごとに1回だけ呼び出しを行います。それはO（n）です。追加された各ディスクの2倍の時間差を表示するのに十分でなければならない

19 = Nであなたの最初の関数のタイミングしようと、効果を確認するために、20、21、22。

Answer 2

標準的なアドバイスは、それが適用されることを保証したい場合は、共通の部分式の最適化を自分で行うことです。 https://wiki.haskell.org/GHC/FAQ#Does_GHC_do_common_subexpression_elimination.3Fを参照してください。

numStepsHanoi :: Integer -> Integer 
numStepsHanoi 0 = 0 
numStepsHanoi n = let steps = numStepsHanoi (n-1) 
        in steps + steps + 1