¿Los compiladores pueden convertir la lógica recursiva en lógica no recursiva equivalente?

He estado aprendiendo F # y está empezando a influir en cómo pienso cuando estoy programando C #. Con ese fin, he estado usando la recursividad cuando siento que el resultado mejora la legibilidad y no puedo imaginar que se vaya a un desbordamiento de pila.

Esto me lleva a preguntarme si los compiladores podrían convertir automáticamente funciones recursivas a una forma no recursiva equivalente.

Sí, algunos lenguajes y compiladores convertirán la lógica recursiva en lógica no recursiva. Esto se conoce como optimización de llamadas de cola : tenga en cuenta que no todas las llamadas recursivas son optimizables. En esta situación, el compilador reconoce una función de la forma:

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

Aquí, el lenguaje puede reconocer que el resultado que se devuelve es el resultado de otra función y cambiar una llamada de función con un nuevo marco de pila en un salto.

Darse cuenta de que el método factorial clásico:

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

no se puede optimizar la llamada de cola debido a la inspección necesaria en la devolución.

Para hacer esta llamada de cola optimizable,

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

Compilar este código con gcc -O2 -S fact.c(el -O2 es necesario para habilitar la optimización en el compilador, pero con más optimizaciones de -O3 se hace difícil para un humano leer ...)

_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

Uno puede ver en el segmento .L4, en jnelugar de un call(que hace una llamada de subrutina con un nuevo marco de pila).

Tenga en cuenta que esto se hizo con C. La optimización de llamadas de cola en java es difícil y depende de la implementación de JVM: tail-recursion + java y tail-recursion + optimization son buenos conjuntos de etiquetas para navegar. Puede encontrar que otros lenguajes JVM pueden optimizar mejor la recursividad de cola (intente clojure (que requiere la recurrencia para optimizar la llamada de cola) o scala).

Ve con cuidado.

La respuesta es sí, pero no siempre, y no todas. Esta es una técnica que tiene diferentes nombres, pero puede encontrar información bastante definitiva aquí y en wikipedia .

Prefiero el nombre "Optimización de llamadas de cola", pero hay otros y algunas personas confundirán el término.

Dicho esto, hay un par de cosas importantes a tener en cuenta:

• Para optimizar una llamada de cola, la llamada de cola requiere parámetros que se conocen en el momento en que se realiza la llamada. Eso significa que si uno de los parámetros es una llamada a la función en sí, entonces no se puede convertir en un bucle, ya que esto requeriría una anidación arbitraria de dicho bucle que no se puede expandir en tiempo de compilación.

• C # no optimiza de manera confiable las llamadas de cola. El IL tiene las instrucciones para hacerlo que emitirá el compilador de F #, pero el compilador de C # lo emitirá de manera inconsistente y, dependiendo de la situación del JIT, el JIT puede o no hacerlo. Todo indica que no debe confiar en que sus llamadas de cola se optimicen en C #, el riesgo de desbordamiento al hacerlo es significativo y real