Parece que he encontrado una forma genérica de convertir cualquier procedimiento recursivo a recursión de cola:

1. Defina un subprocedimiento auxiliar con un parámetro adicional "resultado".
2. Aplique lo que se aplicaría al valor de retorno del procedimiento a ese parámetro.
3. Llame a este procedimiento auxiliar para comenzar. El valor inicial para el parámetro "resultado" es el valor para el punto de salida del proceso recursivo, de modo que el proceso iterativo resultante comienza desde donde el proceso recursivo comienza a reducirse.

Por ejemplo, aquí está el procedimiento recursivo original para convertir ( ejercicio SICP 1.17 ):

(define (fast-multiply a b)
  (define (double num)
    (* num 2))
  (define (half num)
    (/ num 2))
  (cond ((= b 0) 0)
        ((even? b) (double (fast-multiply a (half b))))
        (else (+ (fast-multiply a (- b 1)) a))))

Aquí está el procedimiento convertido, recursivo de cola ( ejercicio SICP 1.18 ):

(define (fast-multiply a b)
  (define (double n)
    (* n 2))
  (define (half n)
    (/ n 2))
  (define (multi-iter a b product)
    (cond ((= b 0) product)
          ((even? b) (multi-iter a (half b) (double product)))
          (else (multi-iter a (- b 1) (+ product a)))))
  (multi-iter a b 0))

¿Alguien puede probar o refutar esto?

Su descripción de su algoritmo es realmente demasiado vaga para evaluarla en este momento. Pero, aquí hay algunas cosas a considerar.

CPS

De hecho, hay una manera de transformar cualquier código en un formulario que use solo llamadas de cola. Esta es la transformación CPS. CPS ( estilo de paso de continuación ) es una forma de expresar código pasando cada función a una continuación. Una continuación es una noción abstracta que representa "el resto de un cálculo". En el código expresado en forma CPS, la forma natural de reificar una continuación es como una función que acepta un valor. En CPS, en lugar de que una función devuelva un valor, aplica la función que representa la continuación actual al ser "devuelto" por la función.

Por ejemplo, considere la siguiente función:

(lambda (a b c d)
  (+ (- a b) (* c d)))

Esto podría expresarse en CPS de la siguiente manera:

(lambda (k a b c d)
  (- (lambda (v1)
       (* (lambda (v2)
            (+ k v1 v2))
          a b))
     c d))

Es feo, y a menudo lento, pero tiene ciertas ventajas:

• La transformación puede ser completamente automatizada. Por lo tanto, no es necesario escribir (o ver) el código en forma de CPS.
• Combinado con thunking y trampolining , se puede usar para proporcionar optimización de cola en idiomas que no ofrecen optimización de cola. (La optimización de la llamada de cola de las funciones recursivas de cola directamente se puede lograr a través de otros medios, como convertir la llamada recursiva en un bucle. Pero la recursión indirecta no es tan trivial para convertir de esta manera).
• Con CPS, las continuaciones se convierten en objetos de primera clase. Dado que las continuaciones son la esencia del control, esto permite que prácticamente cualquier operador de control se implemente como una biblioteca sin requerir ningún soporte especial del lenguaje. Por ejemplo, goto, excepciones y subprocesos cooperativos se pueden modelar utilizando continuaciones.

TCO

Me parece que la única razón para preocuparse por la recursividad de cola (o las llamadas de cola en general) es para fines de optimización de llamadas de cola (TCO). Por lo tanto, creo que una mejor pregunta es "¿mi código de rendimiento de transformación es optimizable por cola?".

Si consideramos una vez más CPS, una de sus características es que el código expresado en CPS consiste únicamente en llamadas de cola. Como todo es una llamada de cola, no necesitamos guardar un punto de retorno en la pila. Entonces, todo el código en forma de CPS debe ser optimizado, ¿verdad?

Bueno, no del todo. Verá, si bien puede parecer que hemos eliminado la pila, todo lo que hemos hecho es simplemente cambiar la forma en que la representamos. La pila ahora es parte del cierre que representa una continuación. Entonces, CPS no hace que todo nuestro código sea optimizado mágicamente.

Entonces, si CPS no puede hacer que todo sea TCO, ¿hay una transformación específica para la recursión directa que pueda? No, no en general. Algunas recursiones son lineales, pero otras no. Las recursiones no lineales (p. Ej., Árbol) simplemente deben mantener una cantidad variable de estado en alguna parte.