list de kotlin de queue

Estoy tratando de hacer algunas operaciones que causarían un StackOverflow en Kotlin justo ahora.

Sabiendo eso, recordé que Kotlin tiene soporte para funciones de tailrec , así que traté de hacerlo:

 private tailrec fun Turn.debuffPhase(): List<Turn> { val turns = listOf(this) if (facts.debuff == 0 || knight.damage == 0) { return turns } // Recursively find all possible thresholds of debuffing return turns + debuff(debuffsForNextThreshold()).debuffPhase() } 

Ante mi sorpresa de que IDEA no lo reconoció como un tailrec , traté de quitarle una function de extensión y convertirla en una function normal:

 private tailrec fun debuffPhase(turn: Turn): List<Turn> { val turns = listOf(turn) if (turn.facts.debuff == 0 || turn.knight.damage == 0) { return turns } // Recursively find all possible thresholds of debuffing val newTurn = turn.debuff(turn.debuffsForNextThreshold()) return turns + debuffPhase(newTurn) } 

Aun así, no es aceptado. Lo importante no es que la última llamada a function sea para la misma function? Sé que + es un signo de la function List plus , pero ¿debería marcar la diferencia? Todos los ejemplos que veo en Internet para la queue de otros idiomas permiten ese tipo de acciones .

Traté de hacer eso con Int también, que parecía ser algo más comúnmente usado que agregar a las lists, pero tuvo el mismo resultado:

 private tailrec fun discoverBuffsNeeded(dragon: RPGChar): Int { val buffedDragon = dragon.buff(buff) if (dragon.turnsToKill(initKnight) < 1 + buffedDragon.turnsToKill(initKnight)) { return 0 } return 1 + discoverBuffsNeeded(buffedDragon) } 

¿No deberían todas esas implementaciones permitir la llamada de queue? Pensé en algunas otras forms de resolver eso (como pasar la list como MutableList en los parameters también), pero cuando es posible trato de evitar el envío de collections a ser cambiadas dentro de la function y esto parece un caso de que esto sea posible.

PD: Sobre el progtwig de preguntas, estoy implementando una solución a este problema .

Ninguno de tus ejemplos es recursivo de queue.

Una llamada final es la última llamada en una subrutina. Una llamada recursiva es una llamada de una subrutina a sí misma. Una llamada recursiva de queue es una llamada final de una subrutina a sí misma.

En todos sus ejemplos, la última llamada es a + , no a la subrutina. Entonces, todos son recursivos (porque se llaman a sí mismos), y todos tienen queue (porque cada subrutina siempre tiene una "última llamada"), pero ninguno de ellos es recursivo de queue (porque la llamada recursiva no es la última llamada).

La notación Infix a veces puede oscurecer la llamada final, es más fácil de ver cuando se escriben todas las operaciones en forma de prefijo o como una llamada a un método:

 return plus(turns, debuff(debuffsForNextThreshold()).debuffPhase()) // or return turns.plus(debuff(debuffsForNextThreshold()).debuffPhase()) 

Ahora es mucho más fácil ver que la llamada a debuffPhase no está en position de queue, sino que es la llamada a plus (es decir, + ) que está en position de queue. Si Kotlin tenía llamadas de queue generales, entonces esa llamada a plus sería eliminada, pero AFAIK, Kotlin solo tiene recursión de queue (como Scala), por lo que no lo hará.

Sin dar una respuesta a su rompecabezas, aquí hay una function no recursiva de la queue.

 fun fac(n: Int): Int = if (n <= 1) 1 else n * fac(n - 1) 

No es una queue recursiva porque la llamada recursiva no está en position de queue, como lo señala la respuesta de Jörg.

Se puede transformar en una function recursiva de queue usando CPS ,

 tailrec fun fac2(n: Int, k: Int = 1): Int = if (n <= 1) k else fac2(n - 1, n * k) 

aunque una mejor interfaz probablemente ocultaría la continuación en una function auxiliar privada.

 fun fac3(n: Int): Int { tailrec fun fac_continue(n: Int, k: Int): Int = if (n <= 1) k else fac_continue(n - 1, n * k) return fac_continue(n, 1) }