ツリー内のノード数を計算する方法は？

Question

私には助けが必要な問題があります。与えられたIm：

int sum(int[] array, int first, int last) 
{ 
if (first == last) 
return array[first]; 
int mid = (first + last)/2; 
return sum(array, first, mid) + sum(array, mid + 1, last); 
} 

質問：再帰ツリーのノード数を数える数式を決定します。

だから、私は、再帰方程式得た： T（N）= 2T（N/2）+ DN

を、長さ8の配列については、例えば、再帰ツリー内のノードの数は15であろうこれは、ツリー内のノードの数が2n-1（nは配列のサイズ）となることを示します。

私の考えが正しいかどうか、2n-1の式をどのようなケースにも適用できるのだろうか？また、再帰的なアルゴリズムでは、再帰ツリーのノード数を計算する一般的な方法はありますか？

ありがとうございました！

Answer 1

 2 
    /\ 
    1 1 // 2(n) - 1 = 2(2) - 1 = 3 seems to match! 

     3 
    /\ 
    2 1 
/\ 
    1 1  // 2(n) - 1 = 2(3) - 1 = 5 which seems to match 

数式2（n） - 1が正しいと思われます。