这里的关键是可视化调用树。一旦这样做，复杂性是：
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)