14

I've recently learned Haskell, and am trying to carry the pure functional style over to my other code when possible. An important aspect of this is treating all variables as immutable, i.e. constants. In order to do so, many computations that would be implemented using loops in an imperative style have to be performed using recursion, which typically incurs a memory penalty due to the allocation a new stack frame for each function call. In the special case of a tail call (where the return value of a called function is immediately returned to the callee's caller), however, this penalty can be bypassed by a process called tail call optimization (in one method, this can be done by essentially replacing a call with a jmp after setting up the stack properly). Does MATLAB perform TCO by default, or is there a way to tell it to?

4

1 に答える 1

11

単純な末尾再帰関数を定義すると、次のようになります。

function tailtest(n)
  if n==0; feature memstats; return; end
  tailtest(n-1);
end

そして、それが非常に深く繰り返されるようにそれを呼び出します：

set(0,'RecursionLimit',10000);
tailtest(1000);

そうすると、スタックフレームが大量のメモリを消費しているようには見えません。ただし、再帰をさらに深くすると、次のようになります。

set(0,'RecursionLimit',10000);
tailtest(5000);

それから（私のマシンでは、今日）MATLABは単にクラッシュします：プロセスは不意に死にます。

これは、MATLABがTCOを実行していることと一致しているとは思いません。関数がそれ自体を末尾呼び出しする場合は、1つの場所でのみ、単一の引数以外のローカル変数はなく、誰もが望むのと同じくらい簡単です。

したがって、いいえ。少なくともデフォルトでは、MATLABはTCOをまったく実行しないようです。私は（これまでのところ）それを可能にするかもしれないオプションを探していません。あったらびっくりします。

スタックを吹き飛ばさない場合、再帰にはいくらかかりますか？Bill Cheathamの回答に対する私のコメントを参照してください。時間のオーバーヘッドは重要ですが、異常ではないようです。

...私がそのコメントを残した後、ビル・チーサムが彼の答えを削除したことを除いて。わかった。そこで、フィボナッチ関数と単純な末尾再帰関数の単純な反復実装を採用し、両方で基本的に同じ計算を実行し、両方のタイミングを調整しましたfib(60)。再帰的な実装は、反復的な実装よりも実行に約2.5倍長くかかりました。もちろん、反復ごとに1回の加算と1回の減算よりも多くの作業を行う関数の場合、相対的なオーバーヘッドは小さくなります。

（私はdelnanの感情にも同意します：Haskellで自然に感じる種類の非常に再帰的なコードは、通常、MATLABでは一義的である可能性があります。）

于 2011-03-16T16:25:34.060 に答える