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

王林
リリース: 2023-09-05 10:01:06
転載
1089 人が閲覧しました

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 サイトの他の関連記事を参照してください。

ソース:tutorialspoint.com
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
最新の問題
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート