¿Por qué es esta cola recursiva?

Question

la salida de este Scala-código:

def rec(n: Int) { 
    if (n > 1) { 
    val d = n/2 
    rec(d) 
// if (d > 1) // abort loop 
     rec(n/d) 
    } 
} 

Este código se traducirá en un bucle sin fin. Debido a la optimización recursiva de la cola, no obtengo un StackOverflowError.

decompilados JAD Tengo este código Java:

public void rec(int n) 
{ 
    int d; 
    for(; n > 1; n /= d) 
    { 
     int i = n; 
     d = i/2; 
     rec(d); 
    } 
} 

En la última línea del bucle el método llama a sí misma, por tanto, no entiendo la posición llamada de cola. ¿Alguien que pueda explicar esto?

Answer 1

No hay una llamada de cola en caso de rec(d). Para rec(N) (donde N > 1) la pila ya no crece después de las llamadas log2(N) (porque después de eso n es igual a 2 o 3 para siempre, y d es 1). Después de eso, es solo un ciclo infinito con llamada interna rec(1) que regresa inmediatamente cada vez. Es por eso que no hay desbordamiento de pila.

Answer 2

En forma recursiva de su método tiene dos llamadas recursivas. StackOverflowError es causado por el último de ellos.

Debido a la optimización de recursión de cola, esa última llamada se convierte en bucle (mientras la primera llamada se mantiene recursiva), por lo tanto tiene bucle infinito en lugar de recursión infinita, y StackOverflowError no sucede.