再帰的な方法でN/2〜Nを1にN/2を加えて合計1〜Nを計算する

Question

1,2,3とNの和を計算する再帰的な方法を作るのに問題がありますが、 （N/2 + 1 ...〜N）で（1,2,3 ... N/2）を加える。

私がこれまで管理するコードはこれです：

public static void main(String[] args) { 

    System.out.println(sum(10, 1)); 
} 

public static int sum(int n, int start) { 

    if (start == n){ 
     return n; 
    } 

    if (start > n/2){ 
     return start + sum(n, start + 1); 
    } 

    return start + sum(n, start + 1); 

} 

私は、これは間違っていると信じて、それは我々がパーツにに再帰アップを分割するより/小さい方がどのようにやる気にさせる必要があり、学校での割り当てであります合計を計算する効率的な方法。 （N/2からNへの1からN/2への数の加算、1からNへの直接の代わりに）。

彼は私たちをこのようにして私たちのために難しくしましたが、私はこれをどうやって行うのかについての考え方を理解することはできません。それが正しいか？

ありがとうございます。

Answer 1

再帰の深さを減らすために役立つ場合があります。

あなたは内側のステップのためのn/2を計算するときに、コードは、おそらく次のようになります考慮に始める取る必要がありますだけのために末尾に余分なチェックを回避スタート

public static int sum(int n, int start) { 
    if (start > n) { 
    return 0; 
    } 

    if (start == n){ 
     return n; 
    } 

    int n2 = (start + n)/2; 
    return sum(n2, start) + sum(n, n2 + 1); 
} 

> nのチェックstartとnが2より小さい場合。

Answer 2

intを宣言したことを確認してください。 n/2は必ずしも期待値を与えるわけではありません。あなたの先生があなたに観察したいと思うトリックだと思います。

Answer 3

私は、このコードはできるだけシンプルだと思いますが、ループでパフォーマンスをチェックできます。私は複雑さに違いは見られません。

class Sums { 

    public static int sumHelp(int n, int start){ 
     if (n == start) return; 
     else return (n + sumHelp(n - 1, start)); 
    } 

    public static int sumByHalf(int n){ 
     return sumHelp(n/2, 0) + sumHelp(n, n/2); 
    } 

    public static int sum(int n){ 
     return sumHelp(n, 0); 
    } 

    public static void main(String[] args) { 
     System.out.println(sumByHalf(100)); 
     System.out.println(sum(100)); 
    } 
}