algorithm - 再帰プログラムを使用した場合のスペースの複雑さの違い

Question

スペースの複雑さが最も低い再帰プログラムと非再帰プログラムのスペースの複雑さの違い (多かれ少なかれ) を知りたいです。また、再帰でのスタックの使用に関する優れたチュートリアルのガイダンスも歓迎します。可能であれば、説明のために短い例も提供してください。

Answer 1

再帰はスペースの複雑さを増加させる可能性がありますが、減少することはありません。たとえば、二分探索木への挿入を考えてみましょう。非再帰的な実装 (while サイクルを使用) は O(1) メモリを使用します。再帰的な実装では、O(h) メモリが使用されます (h はツリーの深さです)。

より正式な方法: 空間複雑度 O(X) の再帰アルゴリズムがある場合、空間複雑度 O(X) の非再帰アルゴリズムが常に存在します (スタックを使用して再帰をシミュレートできます)。しかし、その逆ではありません (上記の例を参照)。

Answer 2

実装言語がTCOをサポートしている場合、末尾再帰を使用してループ反復とまったく同じスペースの複雑さを実現できます。

int acc=1;
(for int i=1; i<=n; i++) {
  acc*=i;
}
return acc;

以下と同じです:

int fact (int i, int acc) {
  if( i == 1) 
     return acc;
  return fact(i--, i*acc);
}
return fact(n);