¿MATLAB realiza la optimización de la cola de llamada?

Question

Recientemente he aprendido Haskell, y estoy tratando de llevar el estilo funcional puro a mi otro código cuando sea posible. Un aspecto importante de esto es tratar todas las variables como inmutables, es decir, constantes. Para hacerlo, muchos cómputos que se implementarían usando bucles en un estilo imperativo se deben realizar usando la recursión, que típicamente incurre en una penalización de memoria debido a la asignación de un nuevo marco de pila para cada llamada de función. En el caso especial de una llamada de cola (donde el valor de retorno de una función llamada se devuelve inmediatamente a la persona que realiza la llamada), esta penalización puede pasar por alto mediante un proceso llamado optimización de llamada de cola (en un método, esto se puede hacer haciendo esencialmente reemplazando una llamada con un jmp después de configurar la pila correctamente). ¿MATLAB realiza el TCO de manera predeterminada, o hay alguna forma de decírselo?

Answer 1

Si defino un simple recursiva de cola función:

function tailtest(n) 
    if n==0; feature memstats; return; end 
    tailtest(n-1); 
end 

y lo llamo para que se recursivo bastante profundamente:

set(0,'RecursionLimit',10000); 
tailtest(1000); 

entonces no se ve como si son marcos de pila comiendo mucha memoria Sin embargo, si lo hago recursivo mucho más profundo:

set(0,'RecursionLimit',10000); 
tailtest(5000); 

a continuación (en mi máquina, en la actualidad) MATLAB simplemente se estrella: el proceso muere sin contemplaciones.

No creo que esto sea consistente con MATLAB haciendo cualquier TCO; el caso donde una función se llama a sí misma, solo en un lugar, sin variables locales que no sean un solo argumento, es casi tan simple como cualquiera podría esperar.

Así que: No, parece que MATLAB no hace TCO en absoluto, al menos de forma predeterminada. Hasta ahora no he buscado opciones que puedan habilitarlo. Me sorprendería si hubiera alguno.

En los casos en que no apagamos la pila, ¿cuánto cuesta la recursividad? Vea mi comentario a la respuesta de Bill Cheatham: parece que el tiempo de sobrecarga no es trivial, pero no es una locura.

... Excepto que Bill Cheatham borró su respuesta después de que dejara ese comentario. DE ACUERDO. Entonces, tomé una implementación iterativa simple de la función de Fibonacci y una simple recursiva de cola, haciendo esencialmente el mismo cálculo en ambos, y los sincronicé ambos en fib(60). La implementación recursiva tomó aproximadamente 2.5 veces más tiempo para ejecutarse que la iterativa. Por supuesto, la sobrecarga relativa será menor para las funciones que hacen más trabajo que una adición y una resta por iteración.

(También estoy de acuerdo con el sentimiento de delnan:. Código altamente recursivo del tipo que se siente natural en Haskell es típicamente probable que sea unidiomatic en MATLAB)