用递归树求解递推公式Tn=Tn2+Tn4+cnc为常数

首先画出递归树，每一层的节点数是上一层的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)。