递归树方法求解递推公式 T(n)=T(n/2)+T(n/4)+cn

首先画出递归树，每一层的节点数是上一层的 1/2 和 1/4 之和，即 1/2n 和 1/4n，因此可以得到递归树的深度为 log(n)。

每个节点的代价都是 cn，因此每层的代价是 cn 乘以该层的节点数，即 cn(1/2n+1/4n)。将所有层的代价加起来就是总代价。

总代价 T(n) = cn(1/2n+1/4n) + cn(1/4n+1/8n) + ... + cn(1/2^k n + 1/4^k n)

因为递归树的深度是 log(n)，所以 k=log(n)，代入上式得到：

T(n) = cn(1/2n+1/4n) + cn(1/4n+1/8n) + ... + cn(1/2^log(n) n + 1/4^log(n) n)

T(n) = cn(1/2n+1/4n+...+1/2^log(n) n) + cn(1/4n+1/8n+...+1/4^log(n) n)

这里需要用到一个公式：

1 + 1/2 + 1/4 + ... + 1/2^k = 2 - 1/2^k

将其代入上式得到：

T(n) = cn(2-1/2^log(n)) + cn(2-1/4^log(n))

T(n) = 2cn - cn/2^log(n) + 2cn - cn/4^log(n)

T(n) = 4cn - cn/2^log(n) - cn/4^log(n)

由于 log(n) 是整数，所以可以将 cn/2^log(n) 和 cn/4^log(n) 分别写成 cn/n 和 cn/n^2，得到：

T(n) = 4cn - cn/n - cn/n^2

T(n) = 4cn(1 - 1/n - 1/n^2)

因此，递推公式 T(n) 的解为 T(n) = 4cn(1 - 1/n - 1/n^2)。