C プログラムの再帰関数に補助スペースを使用しますか?

ここでは、再帰的な関数呼び出しがどのように補助スペースを必要とするかを見ていきます。通常の関数呼び出しとどう違うのでしょうか?

以下に示すような関数があるとします。-

long fact(int n){
   if(n == 0 || n == 1)
      return 1;
   return n * fact(n-1);
}

この関数は再帰関数です。 fat(5) のように呼び出すと、以下に示すようにアドレスがスタック内に格納されます。 -

fact(5) --->
fact(4) --->
fact(3) --->
fact(2) --->
fact(1)

再帰関数が自分自身を何度も呼び出すと、アドレスがスタックに追加されます。したがって、関数が n 回再帰的に呼び出される場合、O(n) の補助スペースが占有されます。ただし、これは、通常の関数が n 回呼び出された場合、空間計算量が O(n) になるという意味ではありません。通常の関数の場合、呼び出されたときにアドレスがスタックにプッシュされます。完了すると、アドレスがスタックからポップされ、呼び出し側関数に入力されます。その後、もう一度電話します。したがって、その複雑さは O(1) です。

以上がC プログラムの再帰関数に補助スペースを使用しますか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。