c - 再帰関数でのGCCコンパイラの動作

Question

数日前、私の教授は言った：

関数は、同じ値で2回呼び出されたときに、結果（以前に計算された値）を再利用します。

ただし、結果（以前に計算された値）はヒープメモリに割り当てられます。

彼は次のようないくつかの例を挙げました：フィボナッチ再帰関数。

彼は間違いを犯しましたか？

Answer 1

関数は、同じ値で 2 回呼び出されると、結果 (以前に計算された値) を再利用します。

デフォルトでは、いいえ。関数をメモ化して、既に計算された結果を再利用することができますが、それにはプログラマー (またはコンパイラーの可能性がありますが、それを行う C コンパイラーは知りません) による特別な介入が必要です。

ほとんどの関数は同じ引数で繰り返し呼び出されることはないため、計算されたすべての値をキャッシュするのは非常にコストがかかり無駄になります。また、キャッシュする価値のある優れたヒューリスティックを見つけるのは非常に困難です。したがって、そのようなことは、キャッシュする価値のある関数についてより多くの知識を持っていることを願っているプログラマーに任されています。

Answer 2

実際、メモ化は C++11 で (ある程度) C++ 標準の一部になりました。新しい C++11 機能を使用した再帰関数の自動メモ化の紹介をご覧ください。

編集：

この質問は、C++ ではなく C に関するものです。私は逃しました。この答えは当てはまりません。私はそれを削除しますが、ここには他にメモ化に関する質問があまりなく、誰かの役に立つ可能性が十分にあります.

Answer 3

gccそれ自体は以前の結果をキャッシュしませんが、もちろん、多くの再帰関数では、以前に計算された値のキャッシュを実装することは完全に理にかなっています。

したがって、彼gccがこのキャッシングを処理すると主張した場合、彼は間違いを犯しました。たぶん、彼はむしろフィボナッチ関数などの特定の実装に言及したのだと思います。

Answer 4

まったく同じではありませんが、gcc が再帰関数のインライン化を実行しているという報告を見てきました。フィボナッチ関数の例を見てみましょうf(x) = f(x - 1) + f(x - 2)。どうやら gcc は f(x - 1) への呼び出しをインラインf(x) = 2f(x - 2) + f(x - 3)化し、末尾再帰の最適化を使用してこれをループにすることができます: f(x) = 2f(x - 2) + 2f(x - 5) + ... + f(x % 3)。もちろん、そこにはまだ再帰がいくらかありますが、それははるかに少なくなっています。