¿Es posible usar call/cc para implementar la recursión?

Question

Me pregunto si es posible definir una función recursiva sin llamar a la función en sí misma en su cuerpo pero de alguna manera usar call/cc en su lugar? Gracias.

Answer 1

Puede implementar un combinador en Y usando call/cc, as described here. (! Muchas gracias a John Cowan para mencionar este post puro) Citando ese puesto, aquí está la ejecución de Oleg:

Corolario 1. combinador Y a través de call/cc - combinador Y sin un auto-aplicación explícita.

(define (Y f) 
    ((lambda (u) (u (lambda (x) (lambda (n) ((f (u x)) n))))) 
    (call/cc (call/cc (lambda (x) x))))) 

caso, se utilizó un hecho que

((lambda (u) (u p)) (call/cc call/cc)) 

y

((lambda (u) (u p)) (lambda (x) (x x))) 

son observacionalmente equivalente.

Answer 2

Tu pregunta es un poco vaga. En particular, parece que desea un sistema que modele llamadas recursivas sin realizar directamente llamadas recursivas, utilizando call/cc. Sin embargo, resulta que puede modelar llamadas recursivas sin hacer llamadas recursivas y también sin usar call/cc. Por ejemplo:

#lang racket 

(define (factorial f n) 
    (if (= n 0) 1 (* n (f f (- n 1))))) 

(factorial factorial 3) 

Puede parecer una trampa, pero es la base del combinador Y. ¿Quizás puedas ajustar el conjunto de restricciones en las que estás pensando?

P.S .: si esto es tarea, por favor citeme!

Answer 3

Me temo que call/cc realmente no tiene mucho que ver con esto. Realmente hay solo dos formas de definir una función recursiva:

• Supongamos que su lenguaje permite definiciones de funciones recursivas; es decir, un cuerpo de función puede referirse a la función de encerrar, o el cuerpo de una función f puede referirse a una función g cuyo cuerpo se refiere a f. En este caso, bueno, solo escríbelo de la manera habitual.
• Si su lenguaje prohíbe ambos, pero todavía tiene funciones de primera clase y lambdas, entonces puede usar un fixed-point combinator como el combinador Y. Usted escribe su función para que tome como argumento adicional una función que representa el paso recursivo; cada lugar donde recurrirías, en cambio invocas ese argumento.

Así que para factorial, se escribe así:

(define (factorial-step recurse n) 
    (if (zero? n) 
     1 
     (* n (recurse (- n 1))))) 

La magia del combinador Y es que construye la función recurse que se alimenta a factorial-step.