Рекурсия в Lua vs. Java

Question

У меня есть рекурсивный алгоритм (в трех разных формах), который вычисляет сумму первых n нечетных положительных целых чисел. Эти алгоритмы предназначены только для обучения, я знаю, что есть лучшие способы решения этой проблемы. Я написал три варианта в Lua и Java, которые я буду называть Lua 1, Lua 2, Lua 3 и Java 1, Java 2 и Java 3. Первые два очень похожи, просто перестроены.

Программы Lua - here, а программы Java - here.

Lua 1 и 2 работают очень хорошо и могут легко достигать n = 100 000 000. Lua 3 попадает в переполнение стека, где n> 16 000.

Java 1 может достигать n = 4000 до того, как ударить стек, пока Java 2 достиг 9000. Java 3 удалось получить до n = 15 000, прежде чем снова нанести переполнение стека.

Может ли кто-нибудь объяснить эти результаты? Почему Java 1, 2 и 3 работают так плохо, в то время как Lua 1 и 2 выполнены так хорошо?

Answer 1

Lua делает tail-call elimination. Например, функция, как это:

function foo (n) 
    if n > 0 then return foo(n - 1) end 
end 

никогда не будет вызывать переполнение стека, независимо от того, какое значение n вы звоните.

В Lua только звонок с формой return func(args) - это вызов хвоста, как то, что делают ваши первые две программы Lua. Но в третьей программе Lua:

return (sumOdds3(n-1)) + (2*n - 1) 

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

Answer 2

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

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

Если вы используете итерации и Deque, вы должны оштрафовать почти нет предела стоимости n

Когда вы работаете очень неэффективный код, вы, как правило, считают, что ли один случай или другой может оптимизировать путь неэффективность может иметь большое значение.

Один из способов более эффективно сделать это

// function to compute the sum of the first n odd positive integers 
public static long sumOdds(long n) { 
    long sumAll = n * (n + 1)/2; 
    long sumEven = n/2 * (n/2 + 1); 
    return sumAll - sumEven; 
} 
public static void main(String[] args) throws Exception { 
    sumOdds(1); 

    long start = System.nanoTime(); 
    long l = sumOdds(Integer.MAX_VALUE); 
    long time = System.nanoTime() - start; 
    System.out.printf("sumOdds(%,d) took %,d ns%n", Integer.MAX_VALUE, time); 
} 

отпечатки

sumOdds(2,147,483,647) took 343 ns