ここでは、再帰的な関数呼び出しがどのように補助スペースを必要とするかを見ていきます。通常の関数呼び出しとどう違うのでしょうか?
以下に示すような関数があるとします。-
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 サイトの他の関連記事を参照してください。