¿Es una función recursiva en Scheme siempre optimizada?

Question

He leído algo sobre la optimización de llamadas de cola en Scheme. Pero no estoy seguro de si entiendo el concepto de las llamadas de cola. Si tengo un código como éste:

(define (fac n) 
    (if (= n 0) 
     1 
     (* n (fac (- n 1))))) 

puede esto ser optimizado, por lo que no tendrá memoria de pila? o sólo puede optimización de llamada puede aplicar a una función como esta:

(define (factorial n) 
    (let fact ([i n] [acc 1]) 
     (if (zero? i) 
      acc 
      (fact (- i 1) (* acc i))))) 

Answer 1

Una forma útil de pensar en las llamadas finales es preguntar "¿qué debe pasar con el resultado de la llamada al procedimiento recursivo?"

La primera función no puede ser cola optimizada, ya que la resultado de la llamada interna a fac debe ser utilizado, y se multiplica por n para producir el resultado de la llamada global a fac.

En el segundo caso, sin embargo, el resultado de la llamada 'externa' al fact es ... el resultado de la llamada interna al fact. No se le debe hacer nada más, y el último valor simplemente puede transmitirse directamente como el valor de la función. Eso significa que no se debe retener ningún otro contexto de función, por lo que simplemente se puede descartar.

El estándar R5RS define 'cola de llamada' mediante el uso de la noción de tail context, que es esencialmente lo que he descrito anteriormente.

Answer 2

No, la primera fac no se puede optimizar.

Cuando se llama a una función, necesita saber el lugar desde el que se llamó para que pueda regresar a esa ubicación una vez que se complete la llamada y usar el resultado de la llamada en cálculos futuros (una función fac).

fact se implementa de forma diferente. Lo último que hace fact es llamarse a sí mismo. No es necesario recordar el lugar desde el que llamamos; en su lugar, podemos realizar una eliminación de llamada final. No hay otras acciones que deban realizarse después de la devolución de fact.