# 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. Commented Apr 23, 2015 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! Commented Apr 23, 2015 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. Commented Apr 23, 2015 at 20:05
• How to deal with recursion formula in Mathematica?Related
– xyz
Commented Apr 24, 2015 at 1:14
• Maybe this answer is help to you:)
– xyz
Commented Apr 24, 2015 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 #? Commented Apr 23, 2015 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 ;) Commented Apr 23, 2015 at 20:46
• Thank you for your detailed explanations. I'll keep your hint in mind ;) Commented Apr 23, 2015 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. Commented Apr 23, 2015 at 21:55