En Mathematica, ¿por qué un reemplazo en una función recursiva no finaliza?

Question

Imagínese he definido un factorial recursiva en Mathematica, así:

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

Evaluación de hecho [10] confirma que la función funciona y termina.

Un ejemplo básico, pero cumple su propósito en esta pregunta. En realidad, mi pregunta se refiere a las definiciones de funciones recursivas en general de todos modos.

que espera la evaluación de las sustituciones siguientes para terminar así:

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

Por desgracia, se ejecuta en un límite de nivel de recursividad:

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

esperaba ver algo como:

2 fact[2-1] 

o simplemente el valor

2 

ACTUALIZACIÓN: Una definición recursiva alternativa de hecho de hace funcionar según lo esperado:

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

Pero este hecho (nunca mejor dicho ;-) hace que sea aún más misterioso para mí: ¿Por qué lo hace comportarse de manera muy diferente?

Mi pregunta es doble:

1. Incluso con la ayuda integrada y buscando en la red en busca de pistas, no puedo explicar por qué insiste en Mathematica, al parecer, manteniendo el resultado simbólico, en lugar de evaluar los resultados 'intermedios' y que terminan muy bien. ¿Quién aventura una explicación viable?

2. ¿Cómo puedo convencer a Mathematica para que funcione de acuerdo con mis expectativas (aparte de utilizar la alternativa con si [])?

Estoy realmente desconcertado por esta, y realmente espero que alguien pueda ayudarme.

/Twan

Answer 1

Tratando u[x_] := x; Trace[x*u[x] /. x -> 2], primero se evalúa x y u[x]. En su caso, entonces, primero intenta evaluar fact[x-1] antes de reemplazar x por 2, y alcanza el límite de recursión.

Attributes[ReplaceAll] muestra que no tiene el atributo HoldFirst, por lo que comienza evaluando su primer argumento. Por ejemplo,

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

da 2 se esperaba, ya que tiene el primer argumento, sustituye, luego libera la bodega, como se pretendía.

Otra manera de hacerlo es

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

pero no lo hace.

Sin duda, alguien dará una mejor explicación pronto, sin embargo.

EDIT: En respuesta a la pregunta de por qué añadió

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

no da lugar a la recursividad infinita: se define de esta manera, se evalúa como factif[x]If[x < 1, 1, x factif[x - 1]], ya x<1 no puede ser evaluada. Por lo que queda de esta forma después del intento de evaluación del primer argumento de ReplaceAll, a continuación, la sustitución se produce etc.

Answer 2

Esto se debe a que está evaluando esto:

fact[x-1] 

antes de que ocurra la sustitución. Simplemente haz fact[x-1] y obtendrás el error.

permite fijar su función fact así:

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

Entonces x fact[x - 1] /. x -> 2 vuelve 2 que parece correcta.

Recuerde que su patrón de argumento de función fact[n_] es extremadamente general. Por ejemplo, permite evaluar algo como fact[Integrate[Sin[x], x]], que probablemente no es algo que pretendas. El uso de fact[n_Integer] es mucho más preciso y permitirá que la función fact actúe de la manera que desee.

Si desea definir esta función aún mejor, puede hacer algo como:

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) 

Así que algo como fact["x"] fallará con un mensaje:

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

Answer 3

Las otras respuestas son correctas : fact evalúa antes de que su argumento sea reemplazado. El problema esencial es que ha definido fact con entradas enteras en mente, y no ha proporcionado una condición de terminal para entradas no enteras. Si por el contrario hizo

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

Entonces fact se quedaría sin evaluar hasta que tenía algo que hacía juego con un número entero positivo.

Es posible que deba envolver su declaración de reemplazo en Evaluate para luego iniciar la definición de fact después de reemplazar su argumento.

Un enfoque alternativo podría ser el uso de una función pura:

# fact[#-1]& @ 2 

que no se debe evaluar antes de tiempo.