Почему этот код не хватает памяти в Java, но не в C?

Question

В java или c я могу написать функцию типа

fun(){
  fun();
}

(игнорируя синтаксические подробности)

В java я получаю исключение OutOfMemory, но в C (и, возможно, в некоторых других языках)кажется, что он работает вечно, как если бы это был бесконечный цикл.Почему я не получаю здесь ошибку OutOfMemory?

Answer 1

Так как ваша функция является примером хвостовой рекурсии , то, скорее всего, компилятор C оптимизирует рекурсию к итерации, заставляя ее бесконечно зацикливаться без сбоев.

Answer 2

Другие ответчики правы, что есть некоторая магия компилятора, которая преобразует хвостовую рекурсию в итерацию, хотя это зависит от настроек оптимизации компилятора. Например, в gcc, если мы скомпилируем с gcc -S -O1 someFile.c (учитывая ваш код), мы получим следующую сгенерированную сборку:

fun:
.LFB2:
        pushq   %rbp
.LCFI0:
        movq    %rsp, %rbp
.LCFI1:
        movl    $0, %eax
        call    fun
        leave
        ret
.LFE2:
        .size   fun, .-fun

Итак, вы можете видеть, что он по-прежнему использует инструкции call / exit / ret для выполнения фактического вызова функции, что приведет к остановке процесса. Как только вы начинаете дальнейшую оптимизацию с помощью gcc -S -O2 someFile.c, мы начинаем понимать:

fun:
.LFB24:
        .p2align 4,,10
        .p2align 3
.L2:
        jmp     .L2
.LFE24:    
        .size   fun, .-fun
        .p2align 4,,15

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

Answer 3

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

int fun() { 1 + fun(); }

Answer 4

Как уже отмечали другие, это оптимизация рекурсии хвостового вызова, выполняемая компилятором Си. Как всегда, это помогает взглянуть на конкретный пример. Без включенной оптимизации gcc (v3.4.6) создает следующий код сборки x86: -

fun:
    pushl   %ebp
    movl    %esp, %ebp
    call    fun
    leave
    ret
    .size   fun, .-fun

Обратите внимание на рекурсивный вызов fun (). Если он выполняется, он в конечном итоге переполнит свой стек и вылетит, но при -O2 gcc выдает:

    fun:
        pushl   %ebp
        movl    %esp, %ebp
.L2:
        jmp     .L2
        .size   fun, .-fun

Заметили бесконечный цикл без инструкции возврата? Это просто выполнится навсегда.

Answer 5

Если реализация языка программирования имеет оптимизацию хвостового вызова , то она скомпилирует эту рекурсию в цикл. Текущая виртуальная машина Java не имеет оптимизации хвостового вызова, поэтому она будет в конечном итоге в java.lang.StackOverflowError.

Возможно, в будущем Java VM будет иметь оптимизацию хвостового вызова, потому что функциональные языки программирования, работающие на JVM (Scala, Clojure и т. Д.), Выиграют от этого (сейчас, по крайней мере, компилятор Scala делает свой собственный хвост). оптимизация вызовов для прямой рекурсии , но AFAIK не для косвенной рекурсии).

Answer 6

В C это может быть оптимизировано как хвостовой рекурсивный вызов.Так что вызов fun() на самом деле не вызывает сам себя;он просто перезапускает функцию (как goto).Другими словами, компилятор обрабатывает его так, как если бы он был написан так:

void fun() {
start:
    goto start;
}

Итак, стек не будет расти.

Answer 7

Ваш компилятор c, вероятно, использует хвостовую рекурсию. Каждый раз, когда вы входите в новую функцию, компьютер добавляет запись в стек. Эта запись указывает, куда ЦП должен вернуться после завершения процедуры. Теперь в случае, указанном выше, так как вызов fun () внутри fun () является последним вызовом функции, компилятор c может оптимизировать стек и вместо этого создать хвостовой вызов. Вы можете использовать это для создания цикла:

int foo(int from, int to)
{
    if (from == to) return from;
    dosomething();
    from ++;
    foo(from, to);
}

Многие языки (например, Erlang) вообще не имеют циклов и вместо этого используют вышеуказанный метод для создания циклов.

Java не поддерживает хвостовую рекурсию.

Answer 8

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

Виртуальная машина Java ограничивает глубину рекурсии до некоторого уровня, поэтому она скоро прекратится.