Вычисление суммы от 1 до N путем добавления от 1 до N/2 с N/2 по N в рекурсивном методе

Question

У меня возникает проблема с рекурсивным методом, который вычисляет сумму от 1,2,3 до N, но делает это добавляя (1,2,3 ... к N/2) с (N/2 + 1 ... N).

кода я управлять до сих пор это:

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); 

} 

Я считаю, что это неправильно, это задание в школе, где мы должны мотивировать, как расщепление рекурсии вверх в на часть является более/меньше, эффективный способ расчета суммы. (добавление чисел от 1 до N/2 с N/2 до N, а не только от 1 до N напрямую).

Он заставил нас сделать этот способ, чтобы сделать его более трудным для нас, но я не могу понять идею о том, как это сделать вообще. Правильно ли это?

Благодаря

Answer 1

Может быть полезно в некоторых случаях, чтобы уменьшить глубину рекурсии.

Вы должны принять начать учитывать при расчете п/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 меньше 2.

Answer 2

Проверьте, что вы получили объявление n как 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)); 
    } 
}