Можно ли реализовать сумму элементов массива эффективней используя рекурсию

Question

Начинаю понемногу разбираться в рекурсивных алгоритмах. Натолкнулся на задачку, где нужно реализовать сумму элементов массива используя рекурсию. Прошу оценить мой код, и можно ли его как-нибудь улучшить. Я не знаю можно ли в этом форуме кидать код на проверку, если нет буду рад если кто-нибудь порекомендует альтернативный сайт. Заранее благодарю.

static int summ(int[] array,int lenghAr){
        if (lenghAr <= 0) {
            return 0;
        } else {
            int numberSum = array[lenghAr-1];
            return summa + numberSum +  summ(array, lenghAr - 1);
        }
    }

Answer 1

Ваш учебный алгоритм (если исправить какие то помарки, которые мешают его скомпилировать) - совершенно правильный.

Я даже позволю себе его вольный перевод на русский:

"Для пустого масива сумма элементов равна нулю. (это основание рекурсии)

Для массива размера n>0 сумма его элементов равна сумме его последнего элемента и сумме элементов массива на единицу меньшей длинны (это шаг рекурсии)"

Теперь пару слов об эффективности.

Вообще "эффективность" - это не очень определенный термин. Более точно говорить об "эффективности алгоритма по времени" или "эффективности алгоритма по памяти".

По умолчанию обычно говорят о эффектиности алгоритма по времени - кто быстрее, тот и лучше.

С банальной точки зрения просто просуммировать элементы массива - быстрее, чем Вашим рекурсивным алгоритмом. Почему? потому, что каждый вызов функции (и просто так, и в составе рекурсивного алгоритма) - это довольно большая работа: нужно сохранить в стеке состояние регистров процессора, передать аргументы, и передать выполнение на адрес функции, которая вызывается. Много обращений к памяти.

Кроме того, как я понимаю (возможно, меня кто нибудь поправит) у Вас происходит передача массива "по значению", то есть, массив при каждом вызове функции копируется в область памяти локальных переменных вызываемой функции. (можете погуглить про "передачу по значению" и "передачу по ссылке").

Как можно остаить алгоритм рекурсивным, но сделать его более эфективным?

Например, можно складывать элементы массива параллельно.

Примерно модификация алгоритма может выглядеть так:

"Взять массив, разделить его пополам. Вычислить сумму элементов массива как суму половинок. Если половинка уже достаточно маленькая - то считать её сумму банальным сопосбом - складывая элементы".

Это тоже рекурсивный алгоритм, просто здесь рекурсия устроена немного иначе.

Вообще, есть примеры рекурсивных алгоритмов, котрые работают быстрее, чем их "наивные" реализации даже в однопоточном режиме (без использования параллельного выполнения шагов рекурсии).

Таким хорошим учебным примером является вычисление чисел Фибоначчи. Требуется вычислить значение функции Fib(n), которая определяется как Fib(n) = Fib(n-1) + Fib(n-2), Fib(0)=Fib(1)=1

При внимательном рассмотрении последовательности рекурсивных вызоов можно заметить, что вычисление F(x) для некторых x происходит по несколько раз, занчит, вычислив их однажды, имеет смысл запомнить результат, и в следующий раз не заниматься вычслениями, а просто взять готовый уже вычисленный результат. Это называется мемоизацией

Эти вопросы, а также понятия восходящей и нисходящей рекурсии неплохо разобраны в следующей короткой (5 страничной) статье

У меня есть субъективное мнение, что в большинстве случаев рекурсии учат неправильно. Начиная с примеров типа "факториала", объясняющий выглядит глупо, когда ученик говорит ему, что для вычисления факториала не нужна рекурсия, а нужен просто цикл.

Значительная часть рекурсий на самом деле разворачивается в цикл. Есть даже языки, котрые умеют делать это на этапе компиляции, и это называют термином "оптимизация хвостовой рекурсии".

Но рекурсия начинает играть всеми своими гранями, когда какая то вещь по своей природе рекурсивна. Или когда другого определения, кроме рекурсии, просто не существует.

Для вычисления чисел Фиббоначчи, правда, есть более эффективное "нерекурсивное" решение: можно "начать с начала", с чисел 1 и 1, и просто дойти до нужного N, последовательно считая 2-е, 3-е и т.п. число Фибоначчи.

БЛОГ НА HUSL

Можно ли реализовать сумму элементов массива эффективней используя рекурсию

Ответы (1 шт):