# Factorial implementation using FixedPoint

I implemented the factorial function:

fact[0] = 1
fact[x_Integer?Positive ] := x*fact[x - 1];


f[4] yields 24 as expected

I tried a different version of the factorial function using FixedPoint. I added factAlt[1] = 1 to help SameTest (or rather Equal) conclude that the same result has been produced (when reaching factAlt[1] and factAlt[0]).

factAlt[0] = 1
factAlt[1] = 1
factAlt[n_ /; n >= 1] := n*factAlt[n - 1]
FixedPoint[factAlt, 4, SameTest -> Equal]


This version does not seem to terminate.

I am new to FixedPoint in Mathematica (and have some mileage in lambda calculus).

Can you advise on how to implement factorial correctly using FixedPoint?

Could the issue be that when factAlt[1] is reached, SameTest does not access factAlt[1] = 1 (which is listed separately) and thus SameTest given will not conclude that factAlt[1] and factAlt[0] are the same (?).

ETA. I clearly misinterpreted the function of FixedPoint. Accepted Lukas Lang's answer which is closest to the spirit of the question.

• Read the documentation for FixedPoint. Or try this: FixedPoint[factAlt, 4, 2]. It keeps applying factAlt to the result, so it just explodes. Aug 8 at 15:19
• Are you really asking "how to implement factorial correctly using FixedPoint"? Or are you just trying to understand why your FixedPoint expression doesn't terminate? Aug 8 at 15:21
• Yes, clearly I was entirely on the wrong track here. The question is how to implement factorial using FixedPoint. Aug 8 at 15:26
• Let's say we had fact[n_]:=FixedPoint[fun,n]. Given, say, 4, we're saying that at some point fun[fun[...fun[fun[4]]...]] becomes fixed at 4!. In particular, f[24]==24. But this must be true for every n, so f[n!]==n! in general. But if f[24]==24, then fact[24]==24 and therefore fact[24] =!= 24!. Aug 8 at 15:42
• Now, there are other ways we could use FixedPoint. Like maybe we use a different structure that keeps track of the level of nesting. E.g. fact[n_]:=First[FixedPoint[fun,{n,n}]] where fun somehow decremented the second element of its argument and continued building the product in its first argument. I haven't worked out the details, but I suspect you could define fun so that it appropriately stayed fixed for {x,0} such that x==n!. Aug 8 at 15:51

FixedPoint is not doing what you think it does: It evaluates the sequence facAlt[4], facAlt[facAlt[4]], etc. This yields $$4!=24$$, $$24!=620448401733239000000000$$, etc. which will never reach a fixed point. Unfortunately, I don't see a good way to use FixedPoint to define the factorial.

One way to try and find an explicit FixedPoint is the following:

1. Instead of relying on Mathematica's evaluation, we implement it ourselves using ReplaceRepeated:

factAlt[4] //. {factAlt[0] -> 1, factAlt[n_] :> n*factAlt[n - 1]}
(* 24 *)

2. We can now note that ReplaceRepeated is effectively ReplaceAll with FixedPoint:

FixedPoint[
ReplaceAll@{factAlt[0] -> 1, factAlt[n_] :> n*factAlt[n - 1]},
factAlt[4]
]
(* 24 *)

• Thanks, I rephrased the question. You answer shows where I went wrong. I want to implement the factorial function using the FixedPoint operator (if possible). Aug 8 at 15:28
• @Michel Also, see my edit for a way to force an explicit FixedPoint into the picture, but it really doesn't gain you anything Aug 8 at 15:50
• thanks. Appreciate the comments and the solution. I added a comment to the question as I'm interested in a broader interpretation as well. Aug 8 at 16:04
• @Michel Is there a reason why you are not simply asking a new question? While you now preserved the original content of your question, your "broader question" is so far removed from the original that all answers/comments are worthless in regards to answering it. I am not saying your new question isn't a good question to ask, simply that it doesn't belong inside this question. The goal of Stackexchange is to produce Q&A posts for single, isolated questions, not constantly evolving discussions. Aug 8 at 16:07

Here's an attempt:

factStep[{0, _}] := {1, 0};
factStep[{f_, 0}] := {f, 0};
factStep[{f_, n_}] := factStep[{n f, n - 1}];

myFact[n_Integer?NonNegative] := First[FixedPoint[factStep, {n, n - 1}]]

• Thanks, just noticed your answer. Kept my original vote for Lang as it came close to what I asked originally. Aug 8 at 16:14
Clear["Global*"]

fac[n_Integer?Positive] :=
FixedPoint[{#[[1]] - 1, Times @@ #} &, {n, 1},
SameTest -> (#1[[2]] == #2[[2]] &)][[-1]]


Test:

And @@ Table[fac[n] == n!, {n, 1, 10}]

(* True *)


There is no need for FixedPoint. The definition alone will do what you want:

factAlt[0] = 1
factAlt[1] = 1
factAlt[n_ /; n >= 1] := n*factAlt[n - 1]
factAlt[4]

(* 24 *)
`
• I realise this. I just wonder if it can be done. Aug 8 at 15:34