Ist es möglich, call/cc zu verwenden, um Rekursion zu implementieren?

Question

Ich frage mich, ob es möglich ist, eine rekursive Funktion zu definieren, ohne die Funktion selbst in ihrem Körper aufzurufen, aber stattdessen call/cc zu verwenden? Vielen Dank.

Answer 1

Sie können einen Y-Kombinator mit call/cc, as described here implementieren. (! Vielen Dank an John Cowan für diesen ordentlichen Beitrag zu erwähnen) Zitiert diesen Posten, hier Olegs Umsetzung:

Folgerung 1. Y Combinator über call/cc - Y Combinator ohne eine explizite Selbstanwendung.

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

Hier haben wir eine Tatsache, dass

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

und

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

beobachtungs gleichwertig sind.

Answer 2

Ihre Frage ist ein bisschen vage. Insbesondere klingt es so, als ob Sie ein System wollen, das rekursive Aufrufe modelliert, ohne direkt rekursive Aufrufe durchzuführen, indem Sie call/cc verwenden. Es stellt sich jedoch heraus, dass Sie rekursive Aufrufe modellieren können, ohne rekursive Aufrufe durchzuführen, und auch, ohne call/cc zu verwenden. Zum Beispiel:

#lang racket 

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

(factorial factorial 3) 

Das mag wie Betrug scheint, aber es ist die Grundlage des Y Combinator. Vielleicht können Sie die Einschränkungen, an die Sie denken, straffen?

P.S .: wenn dies Hausaufgaben sind, bitte zitieren Sie mich!

Answer 3

Ich fürchte, call/cc hat nicht wirklich viel damit zu tun. Es gibt wirklich nur zwei Möglichkeiten zum Definieren einer rekursiven Funktion:

• Angenommen, Ihre Sprache erlaubt rekursive Funktionsdefinitionen; h. ein Funktionskörper kann sich auf die umschließende Funktion beziehen, oder der Rumpf einer Funktion f kann sich auf eine Funktion g beziehen, deren Körper sich auf f bezieht. In diesem Fall schreibst du es einfach auf die übliche Weise.
• Wenn Ihre Sprache verbietet beide, aber es hat immer noch erstklassige Funktionen und Lambdas, dann können Sie eine fixed-point combinator wie der Y-Kombinator verwenden. Sie schreiben Ihre Funktion so, dass es als zusätzliches Argument eine Funktion benötigt, die den rekursiven Schritt darstellen soll; an jedem Ort, an dem du rekurrieren würdest, rufe du stattdessen dieses Argument auf.

Also für factorial, schreiben Sie es wie folgt aus:

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

Die Magie des Y Combinator ist, dass es die recurse Funktion konstruiert, die factorial-step zugeführt werden würde.