W Mathematica, dlaczego zastąpienie w funkcji rekurencyjnej nie kończy się?

Question

Wyobraźmy mam zdefiniowane rekurencyjnej silnia w Mathematica, tak:

Clear[fact] 
fact[0] = 1 
fact[n_] := n fact[n - 1] 

Ocenianie fakt [10] potwierdza, że ​​funkcja działa i kończy.

Trochę przykładowego zszywki, ale służy temu celowi. W rzeczywistości moje pytanie dotyczy ogólnie definicji funkcji rekursywnych.

Spodziewałem oceny następującą wymianę wypowiedzenia, a także:

x fact[x-1] /. x -> 2 

Niestety, biegnie do granicy głębokości rekurencji:

$RecursionLimit::reclim: Recursion depth of 256 exceeded. 

Spodziewałem się zobaczyć coś takiego:

2 fact[2-1] 

lub tylko wartość

2 

UPDATE: Alternatywą rekurencyjna definicja rzeczywistościrobi pracy zgodnie z oczekiwaniami:

Clear[fact] 
fact[n_] := If[n < 1, 1, n fact[n - 1]] 

Ale ten fakt (pun przeznaczone ;-) czyni go jeszcze bardziej tajemniczy do mnie: Dlaczego to robi zachowywać się tak różnie?

Moje pytanie jest dwojaki:

1. Nawet z wbudowaną pomoc i przeszukiwania sieci w poszukiwaniu wskazówek, nie mogę wyjaśnić, dlaczego w Mathematica nalega, najwyraźniej, utrzymując wynik symboliczne, zamiast oceny "pośrednie" wyniki i ładnie się kończą. Kto podejmuje sensowne wytłumaczenie?

2. Jak przekonać Mathematica do działania zgodnie z moimi oczekiwaniami (inne niż użycie alternatywy przy użyciu If [])?

Naprawdę jestem zdziwiony tym, i naprawdę mam nadzieję, że ktoś tam może mi pomóc.

/Twan

Answer 1

Próbując u[x_] := x; Trace[x*u[x] /. x -> 2], najpierw ocenia x i u[x]. W twoim przypadku najpierw próbuje ocenić fact[x-1] przed zastąpieniem x przez 2 i uderza w limit rekursji.

Attributes[ReplaceAll] pokazuje, że nie ma atrybutu HoldFirst, więc zaczyna się od oceny pierwszego argumentu. Na przykład,

ReleaseHold@ReplaceAll[Hold[x*fact[x - 1]], x -> 2] 

daje oczekiwany 2, gdyż posiada pierwszy argument, zastępuje, a następnie zwalnia blokadę, jak zamierzałeś.

Innym sposobem na to jest

Unprotect[ReplaceAll] 
SetAttributes[ReplaceAll, HoldFirst] 
ReplaceAll[x*fact[x - 1], x -> 2] 

ale nie rób tego.

Wkrótce ktoś da lepsze wyjaśnienie.

EDIT: W odpowiedzi na pytanie, dodanego dlaczego

Clear[factif] 
factif[n_] := If[n < 1, 1, n factif[n - 1]] 

nie spowoduje nieskończonej rekurencji: Zdefiniowana w ten sposób, factif[x] ocenia się If[x < 1, 1, x factif[x - 1]], ponieważ x<1 nie można ocenić. Więc pozostaje w tej formie po próbie oceny pierwszego argumentu ReplaceAll, wówczas następuje wymiana itp

Answer 2

To dlatego, że jesteś oceny to:

fact[x-1] 

zanim zajął się dzieje. Po prostu wykonaj fact[x-1], a otrzymasz błąd.

można naprawić funkcję fact tak:

Clear[fact] 
fact[0] = 1 
fact[n_Integer?Positive] := n fact[n - 1] 

Następnie x fact[x - 1] /. x -> 2 powraca 2 co wydaje się prawidłowe.

Pamiętaj, że twój wzorzec argumentów funkcji fact[n_] to wyjątkowo ogólnie. Na przykład pozwala na ocenę czegoś takiego, jak fact[Integrate[Sin[x], x]], co prawdopodobnie nie jest zamierzonym zadaniem. Używanie fact[n_Integer] jest o wiele bardziej precyzyjne i pozwoli funkcji fact działać tak, jak chcesz.

Jeśli chcesz zdefiniować tę funkcję nawet lepiej, można zrobić coś takiego:

Clear[fact] 
fact::nicetrybuddy = "fact[``] is not defined."; 
fact[0] = 1 
fact[n_Integer?Positive] := n fact[n - 1] 
fact[n_] := (Message[fact::nicetrybuddy, n]; $Failed) 

Tak, że coś fact["x"] zakończy się niepowodzeniem z komunikatem:

fact::nicetrybuddy: fact[x] is not defined. 

Answer 3

Pozostałe odpowiedzi są poprawne : fact oblicza przed zastąpieniem argumentu. Zasadniczą kwestią jest to, że zdefiniowałeś fact z myślą o wejściach całkowitych i nie dostarczyłeś warunku terminala dla wejść niecałkowitych. Jeśli zamiast tego zrobił

Clear[fact] 
fact[0] = 1 
fact[n_Integer?Positive] := n fact[n - 1] 

Następnie fact pozostałoby unevaluated aż coś pasującego dodatnia.

Być może trzeba będzie zastąpić oświadczenie zastępcze Evaluate, aby następnie zwolnić definicję dla fact po zastąpieniu jej argumentu.

Alternatywnym rozwiązaniem może być użycie czystego funkcję:

# fact[#-1]& @ 2 

To nie powinno oceniać się przedwcześnie.