Могут ли компиляторы преобразовывать рекурсивную логику в эквивалентную нерекурсивную логику?

Я изучаю F #, и это начинает влиять на то, как я думаю, когда я программирую на C #. С этой целью я использовал рекурсию, когда чувствую, что результат улучшает читабельность, и я не могу представить, что это приведет к переполнению стека.

Это заставляет меня спросить, могут ли компиляторы автоматически преобразовывать рекурсивные функции в эквивалентную нерекурсивную форму?

Да, некоторые языки и компиляторы преобразуют рекурсивную логику в нерекурсивную логику. Это известно как оптимизация хвостовых вызовов - обратите внимание, что не все рекурсивные вызовы являются оптимизируемыми хвостовыми вызовами. В этой ситуации компилятор распознает функцию вида:

int foo(n) {
  ...
  return bar(n);
}

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

Поймите, что классический метод факториала:

int factorial(n) {
  if(n == 0) return 1;
  if(n == 1) return 1;
  return n * factorial(n - 1);
}

не является хвостовым вызовом, оптимизируемым из-за проверки, необходимой при возврате.

Чтобы сделать этот хвостовой вызов оптимизируемым,

int _fact(int n, int acc) {
    if(n == 1) return acc;
    return _fact(n - 1, acc * n);
}

int factorial(int n) {
    if(n == 0) return 1;
    return _fact(n, 1);
}

Компиляция этого кода с помощью gcc -O2 -S fact.c(-O2 необходима для включения оптимизации в компиляторе, но с большей оптимизацией -O3 человеку становится трудно читать ...)

_fact:
.LFB0:
        .cfi_startproc
        cmpl    $1, %edi
        movl    %esi, %eax
        je      .L2
        .p2align 4,,10
        .p2align 3
.L4:
        imull   %edi, %eax
        subl    $1, %edi
        cmpl    $1, %edi
        jne     .L4
.L2:
        rep
        ret
        .cfi_endproc

Можно увидеть в сегменте .L4, jneа не call(который выполняет вызов подпрограммы с новым кадром стека).

Обратите внимание, что это было сделано с C. Оптимизация вызовов Tail в java сложна и зависит от реализации JVM - tail-recursion + java и tail-recursion + оптимизация - хорошие наборы тегов для просмотра. Вы можете найти другие языки JVM способны оптимизировать хвостовую рекурсию лучше (попытка Clojure (который требует повторялся для оптимизации хвостового вызова), или Скале).

Действуй осторожно.

Ответ да, но не всегда, и не все из них. Это техника, которая называется несколько разных имен, но вы можете найти довольно определенную информацию здесь и в Википедии .

Я предпочитаю название «Оптимизация вызовов», но есть и другие, и некоторые люди будут путать этот термин.

Тем не менее, есть пара важных вещей для реализации:

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

• C # не надежно оптимизирует хвостовые вызовы. У IL есть инструкция, чтобы сделать это, что будет генерировать компилятор F #, но компилятор C # будет генерировать его непоследовательно, и в зависимости от ситуации JIT, JIT может или не может делать это вообще. Все указывает на то, что вы не должны полагаться на свои хвостовые вызовы, оптимизированные в C #, риск переполнения при этом является значительным и реальным