再帰関数の空間の複雑さ
Space Complexity Recursive Function
解決：
これらのタイプの問題に取り組むための便利な方法は、再帰ツリーを考えることです。識別する再帰関数の2つの機能は次のとおりです。
- 木の深さ（合計数 returnステートメント ベースケースまで実行されます）
- 木の幅（合計でいくつ 再帰関数呼び出し できるでしょう）
この場合の漸化式は次のとおりです。T（n）= 2T（n-1）。あなたが正しく指摘したように、時間計算量はO（2 ^ n）ですが、繰り返しツリーに関連して見てみましょう。
C / / T（n-1）T（n-1）C ____ / ____ / CC / / / / T（n-2）T（n-2）T（n-2 ）T（n-2）このパターンは、次の画像のようなベースケースまで続きます。
連続するツリーレベルごとに、nは1ずつ減少します。したがって、ツリーには nの深さ ベースケースに到達する前に。各ノードには2つのブランチがあり、合計レベルがnあるため、ノードの総数は次のようになります。2 ^ n時間計算量を増やすO（2 ^ n）。
各関数呼び出しはプログラムスタックに格納されるため、メモリの複雑さはreturnステートメントの数によって決まります。一般化すると、再帰関数のメモリの複雑さは次のようになります。O（再帰の深さ）。ツリーの深さが示すように、合計n個のreturnステートメントがあるため、メモリの複雑さは次のようになります。オン）。
これが私がそれについてどう思うかです：
- 結局のところ、O（2 ^ N）の再帰呼び出しごとにメモリを割り当てる必要があるため、スペースの複雑さもO（2 ^ N）になるという誘惑に駆られます。 （正しくない）
- 実際には、値は各呼び出しで加算/折りたたみされるため、 スペース 必要なのは、ベースケースから始まり、配列[f（1）、f（2）、f（3）... f（n）]を形成する各呼び出しの結果です。つまり、O（ n）メモリ
