# Express recursion formula by Nest function

I'm fairly new to Mathematica and I have to express a formula by Mathematicas Nest-function. I'd like to find the solution for my formula by my own, thats why I dont want to provide the formula I'm sitting on. But to give an Idea of what I nee I'd like to provide an similar function like f(n):=n*f(n-1) as an example. My problem is that i have to use n and n-1 in my formula. I tried to solve it by using pure functions:

MyFunc[n_]:=Nest[#*(#-1)&,n,n]


but this results into wrong results. How to express a recursion formula like my f(n) (Faculty) by Mathematicas Nest-function?

• If you want to solve a difference equation, i.e. find an expression for f[n], then RSolve is your friend. – Marius Ladegård Meyer Apr 23 '15 at 19:48
• "I have to express a formula by Mathematicas Nest-function". Are you sure about that? It's possible with Nest, but not in an obvious way that's easy to understand for a newcomer. Oftentimes constraints like "have to use ..." are unknowingly self-imposed. And here's another tip: recurrence equations are the discrete analogues to differential equations, and to solve either of them numerically you always need some initial or terminal condition. n*f(n-1) is only factorial if you initialize f properly. If you set f(1)=17, you don't get the factorial. Good luck! – Andreas Lauschke Apr 23 '15 at 19:59
• Thanks so far. Yes I have to use Nest. It is a challenge. I know, the factorial function needs an initial value. In other words: any ideas how n! could be modeld by using Nest? @kguler nope. But thank you anyway! I'm glad about any idea and input to get rid of Nest and pure functions. – Marschal Apr 23 '15 at 20:05
• How to deal with recursion formula in Mathematica?Related – xyz Apr 24 '15 at 1:14
• Maybe this answer is help to you:) – xyz Apr 24 '15 at 1:16

As mentioned in my comment, if you want to actually solve a difference equation, then you should use RSolve. However, on reading your question again, this does not seem to be what you want, but in fact to program a recursive function.

For your example, the factorial, you can use "ordinary" functions with named patterns like this:

fac[0] = 1;
fac[n_] := n fac[n-1]


Or you can use memoization if you want to compute lots of factorials:

fac[0] = 1;
fac[n_] := fac[n] = n fac[n-1]


This stores already computed values in memory, avoiding recursion all the way to n = 1 each time.

If you want to use pure functions, as you seem to want, you call the pure function itself with #0, but as @Andreas Lauschke states, you need to impose the correct initial condition. If you really really want to use Nest and not Fold, you can do

fac2[n_] := Last@Nest[{First@#1 + 1, First@#1*Last@#1} &, {1, 1}, n]


I guess? But except as a challenge, why bother...?

EDIT: I could have written # instead of #1, but writing #1 is a habit since I often make pure functions with more than one argument.

Now for the explanation. Since Nest only applies a function to one expression many times, I need it to act on something which both contains what I'm going to multiply next, and what has already been multiplied. So the pure function meets a list containing {k=First@#1,k!=Last@#1} and returns {k+1,(k+1)!}. After the Nesting is done, I extract the factorial using the first Last@. Since I need to keep track of what k I am at anyway, I could have used

fac3[n_] := Fold[#2*#1 &, 1, Range[n]]


which is much better that Nest in my opinion (but still far worse than the memoized one or the built-in Factorial).

• fac2 seems to do the job. Why bothering? Ambition i think ;). Anyway could you elaborate a little bit more on your solution or is there maybe a possibility to show how Mathematica assembles your formula? Your creating a List, but what exactly First@#1 or Last@#1 are doing. And why #1 and not simply #? – Marschal Apr 23 '15 at 20:30
• @Marschal I have added some explanations to my answer. Also thanks for the accept, but in the future, don't accept an answer straight away, there may be persons with much better answers out there who are now discouraged from answering ;) – Marius Ladegård Meyer Apr 23 '15 at 20:46
• Thank you for your detailed explanations. I'll keep your hint in mind ;) – Marschal Apr 23 '15 at 20:52

If you insist on Nest ...

MyFunc[n_]:=Module[{k=0},
Nest[(k++;k #)&,1,n]
];

• Thanks a lot for your answer. Yours is short and doesn't need a list! Anyway i'd like to accept Marius Ladegård Meyer's answer, hence he gave an in depth explanation on his solution. – Marschal Apr 23 '15 at 21:55