关键在于将调用树形象化。完成后，复杂性为：
nodes of the call tree * complexity of other code in the function
后一个术语的计算方式与普通迭代函数相同。
相反，完全二叉树的总节点数可以通过以下方式计算：
C^L - 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) {
}
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)。
