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.Czy można użyć wywołania/cc do implementacji rekursji?
Odpowiedz
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.
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!
Cóż, już znałem tę sztuczkę do rekursji. Zastanawiam się, czy istnieje sposób niezależny od używania call/cc do zdefiniowania funkcji rekursywnej, powiedzmy 'factorial'. To nie jest ćwiczenie domowe! Dzięki. – day
@plmday Rozwiązanie Johna już nie jest samoindeksujące. Czego więcej potrzebujesz od 'call/cc'? –
@ SamTobin-Hochstadt Cóż, to znaczy, 'f' odnosi się do siebie, czyż nie?Chcę zobaczyć, jak daleko możemy się posunąć za pomocą 'call/cc', w szczególności, biorąc pod uwagę jego zdolność, możemy użyć go do symulacji zwykłego lub niecodziennego sposobu definiowania funkcji rekursywnej. – day
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
.
Niesamowite, dokładnie to, co chcę. Wielkie dzięki. – day
@wberry Postanowiłem znaleźć sposób na zacytowanie tego fragmentu kodu, który, mam nadzieję, będzie bardziej zgodny z zasadami "dozwolonego użytku". –
Bardzo dobrze, dziękuję. – wberry