ここで重要なのは、コールツリーを視覚化することです。それが完了すると、複雑さは次のようになります。
nodes of the call tree * complexity of other code in the function
後者の項は、通常の反復関数の場合と同じ方法で計算できます。
代わりに、完全なツリーの合計ノードは次のように計算されます。
C^L - 1
------- , when C>1
/ C - 1
/
# of nodes =
\
\
L , when C=1 (this is special case of a single branch tree)
ここで、Cは各ノードの子の数であり、Lはツリーのレベルの数です（ルートを含む）。
ツリーを視覚化するのは簡単です。最初の呼び出し（ルートノード）から開始し、関数内の再帰呼び出しの数と同じ数の子を描画します。サブコールに渡されるパラメータを「ノードの値」として記述することも役立ちます。
したがって、上記の例の結果は次のとおりです。
int recursiveFun1(int n)
{
if (n <= 0)
return 1;
else
return 1 + recursiveFun1(n-1);
}
まず、コールツリーについて考えます。
n level 1
n-1 level 2
n-2 level 3
n-3 level 4
... ~ n levels -> L = n
ここで、ノードあたりの子の数はC = 1であり、レベルの数はL = n+1です。残りの関数の複雑さはO（1）です。したがって、全体の複雑さはL * O（1）=（n + 1）* O（1）= O（n）です。
int recursiveFun2(int n)
{
if (n <= 0)
return 1;
else
return 1 + recursiveFun2(n-5);
}
ここでの呼び出しツリーは次のとおりです。
n
n-5
n-10
n-15
... ~ n/5 levels -> L = n/5
ここでもC=1ですが、L = n/5です。残りの関数の複雑さはO（1）です。したがって、全体の複雑さはL * O（1）=（n / 5）* O（1）= O（n）です。
int recursiveFun3(int n)
{
if (n <= 0)
return 1;
else
return 1 + recursiveFun3(n/5);
}
コールツリーは次のとおりです。
n
n/5
n/5^2
n/5^3
... ~ log5(n) levels -> L = log5(n)
したがって、C = 1、L = log（n）です。残りの関数の複雑さはO（1）です。したがって、全体の複雑さはL * O（1）= log5（n）* O（1）= O（log（n））です。
void recursiveFun4(int n, int m, int o)
{
if (n <= 0)
{
printf("%d, %d\n",m, o);
}
else
{
recursiveFun4(n-1, m+1, o);
recursiveFun4(n-1, m, o+1);
}
}
ここでは、呼び出しツリーはより複雑です。
n level 1
n-1 n-1 level 2
n-2 n-2 n-2 n-2 ...
n-3 n-3 n-3 n-3 n-3 n-3 n-3 n-3 ...
... ~ n levels -> L = n
ここで、ノードあたりの子の数はC = 2ですが、L=nです。残りの関数の複雑さはO（1）です。今回は、C> 1であるため、呼び出しツリー内のノード数の完全な式を使用します。したがって、全体の複雑さは（C ^ L-1）/（C-1）* O（1）=（2 ^ n-1）です。 ）* O（1）= O（2 ^ n）。
int recursiveFun5(int n)
{
for (i = 0; i < n; i += 2) {
// do something
}
if (n <= 0)
return 1;
else
return 1 + recursiveFun5(n-5);
}
繰り返しますが、呼び出しツリーは次のとおりです。
n
n-5
n-10
n-15
... ~ n/5 levels -> L = n/5
ここで、C = 1、L = n/5です。残りの関数の複雑さはO（n）です。したがって、全体の複雑さはL * O（1）=（n / 5）* O（n）= O（n ^ 2）です。