Czy można użyć wywołania/cc do implementacji rekursji?

Question

Zastanawiam się, czy możliwe jest zdefiniowanie funkcji rekursywnej bez wywoływania samej funkcji w jej ciele, ale w jakiś sposób za pomocą wywołania/cc zamiast tego? Dzięki.

Answer 1

Można zastosować kombinator Y przy użyciu call/cc, as described here. (! Wiele dzięki John Cowan dla wspomnieć Ten gustowny post) Cytowanie tego posta, oto realizacja Olega:

WNIOSEK 1. Y combinator poprzez call/cc - Y Combinator bez wyraźnego samodzielnego stosowania.

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

Tutaj użyliśmy fakt

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

i

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

są obserwacyjnie równoważne.

Answer 2

Twoje pytanie jest nieco niejasne. W szczególności brzmi to tak, jakbyś chciał systemu, który modeluje wywołania rekursywne bez wykonywania bezpośrednio wywołań rekursywnych, za pomocą połączenia/cc. Okazuje się jednak, że można modelować wywołania rekursywne bez wykonywania wywołań rekursywnych i również bez użycia połączenia/cc. Na przykład:

#lang racket 

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

(factorial factorial 3) 

To może wydawać się oszustwem, ale jest podstawą kombinatora Y. Być może możesz zaostrzyć zestaw ograniczeń, o których myślisz?

P.S .: jeśli to praca domowa, proszę zacytuj mnie!

Answer 3

Obawiam się, że call/cc tak naprawdę nie ma wiele wspólnego z tym. Istnieją naprawdę tylko dwa sposoby definiowania funkcji rekursywnej:

• Załóżmy, że twój język pozwala na definicje funkcji rekursywnych; to znaczy, że korpus funkcji może odnosić się do funkcji otaczającej, lub ciało funkcji może odnosić się do funkcji, która odnosi się do . W takim przypadku, po prostu zapisz to w zwykły sposób.
• Jeśli twój język zabrania obu tych funkcji, ale nadal ma funkcje pierwszej klasy i lambdy, możesz użyć kombinacji fixed-point combinator, takiej jak kombinator Y. Piszecie swoją funkcję, aby jako dodatkowy argument przyjąć funkcję, która ma reprezentować etap rekursywny; w każdym miejscu, w którym powracasz, zamiast tego przywołujesz ten argument.

Więc dla factorial, piszesz to tak:

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

Magia combinator Y jest to, że tworzy funkcję recurse który byłby podawany do factorial-step.