采用递归树求解以下递归方程；T(1)=1 T(n)=4T(n/2)+n 当n>1时

首先画出递归树：

      n
      |
    __|__
   |     |
  n/2    n/2
  |      |
__|__  __|__
|   |  |   |
n/4 n/4 n/4 n/4

可以发现，每层的结点数都是原来层的两倍，而第一层只有一个结点。因此，第k层的结点数为2^(k-1)。

接下来计算每层的代价总和。第一层代价为T(1) = 1。对于每个子问题T(n/2)，代价都是4倍，因此第二层代价总和为4T(n/2)。同理，每层的代价总和也是4倍。因此，第k层的代价总和为4^k T(n/2^k)。

当子问题的规模降至1时停止递归。也就是说，当n/2^k = 1时，求解就停止了。解出k = log2(n)。

因此，总代价为：

T(n) = 1 + 4T(n/2) + 4^2T(n/4) + ... + 4^(log2(n)-1)T(1)
= 1 + 4T(n/2) + 4^2T(n/4) + ... + 4^(log2(n)-1)
= 1 + 4(1 + 4T(n/4) + 4^2T(n/8) + ... + 4^(log2(n)-2))
+ 4^(log2(n)-1)
= 1 + 4 + 4^2T(n/4) + ... + 4^(log2(n)-1)
= 1 + 4 + 4^2 + ... + 4^(log2(n)-1)
= (4^log2(n) - 1) / (4 - 1)
= 3n - 1

因此，递归方程的解为T(n) = 3n - 1。