Почему в Mathematica замена в рекурсивной функции не заканчивается? - PullRequest
Новая
       15

Почему в Mathematica замена в рекурсивной функции не заканчивается?

7 голосов
/ 19 ноября 2011

Представьте, что я определил рекурсивный факториал в Mathematica, например: 

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

Факт оценки [10] подтверждает, что функция работает и завершается.

Немного основной пример, но он служит своей цели в этом вопросе. На самом деле, мой вопрос в любом случае относится к рекурсивным определениям функций.

Я ожидал, что оценка следующей замены также прекратится: 

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

Увы, он достигает предела глубины рекурсии: 

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

Я ожидал увидеть что-то вроде: 

2 fact[2-1]

или просто значение 

2

ОБНОВЛЕНИЕ: альтернативное рекурсивное определение факт работает как ожидалось: 

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

Но этот факт (каламбур ;-) делает его еще более загадочным для меня: почему он ведет себя так по-разному?

У меня двоякий вопрос:

  1. Даже со встроенной справкой и поиском подсказок я не могу объяснить, почему Mathematica настаивает на сохранении символического результата, а не на оценке «промежуточных» результатов и приятном завершении. Кто рискует дать объяснение?

  2. Как я могу убедить Mathematica действовать в соответствии с моими ожиданиями (кроме использования альтернативы с использованием If [])?

Я действительно озадачен этим, и я очень надеюсь, что кто-то там может мне помочь.

/ Twan

Ответы [ 3 ]

6 голосов
/ 19 ноября 2011

Пытаясь u[x_] := x; Trace[x*u[x] /. x -> 2], сначала оцениваются x и u[x]. Тогда в вашем случае он сначала пытается оценить fact[x-1], прежде чем заменить x на 2, и достигает предела рекурсии.

Attributes[ReplaceAll] показывает, что у него нет атрибута HoldFirst, поэтому он начинает с оценки своего первого аргумента. Например, 

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

дает ожидаемое 2, поскольку содержит первый аргумент, заменяет, а затем освобождает удержание, как вы и предполагали.

Еще один способ сделать это - 

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

но не делай этого.

Конечно, кто-то скоро даст лучшее объяснение.

РЕДАКТИРОВАТЬ: В ответ на добавленный вопрос о том, почему 

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

не приводит к бесконечной рекурсии: при таком определении factif[x] оценивается как If[x < 1, 1, x factif[x - 1]], поскольку x<1 не может быть оценено. Таким образом, он остается в этой форме после попытки вычисления первого аргумента ReplaceAll, затем происходит замена и т. Д.

5 голосов
/ 19 ноября 2011

Это потому, что вы оцениваете это: 

fact[x-1]

до замены.Просто сделайте fact[x-1], и вы получите ошибку.

Вы можете исправить свою fact функцию следующим образом: 

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

Тогда x fact[x - 1] /. x -> 2 вернет 2, что кажется правильным.

Помните, что ваш шаблон аргумента функции fact[n_] является чрезвычайно общим.Например, он позволяет оценить что-то вроде fact[Integrate[Sin[x], x]], что, вероятно, не то, что вы намеревались.Использование fact[n_Integer] гораздо точнее и позволит функции fact действовать так, как вы хотите.

Если вы хотите определить эту функцию еще лучше, вы можете сделать что-то вроде: 

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)

Чтобы что-то вроде fact["x"] не получилось с сообщением: 

fact::nicetrybuddy: fact[x] is not defined.
1 голос
/ 19 ноября 2011

Остальные ответы верны: fact вычисляется до замены аргумента.Существенная проблема заключается в том, что вы определили fact с учетом целочисленных входов и не предоставили условие терминала для нецелых входов.Если бы вы вместо этого сделали 

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

, тогда fact останется без оценки до тех пор, пока в нем не будет что-то, совпадающее с положительным целым числом.

Возможно, вам придется заключить оператор замены в Evaluateзатем запустите определение для fact после замены его аргумента.

Альтернативный подход может заключаться в использовании чистой функции: 

# fact[#-1]& @ 2

Это не должно оцениваться преждевременно.

...