2

Mathematica can solve recursive equations using RSolve. Is it possible to have a function defined by a recurrence, regardless whether the recurrence can or cannot be solved analytically?

Dr. belisarius
  • 60,527
  • 15
  • 115
  • 190
malina
  • 121
  • 1
  • 1
  • 3
  • The recurrence relation is independent of your (or Mma) ability to find a closed form. Could you explain your question further? (please Edit it by clicking here http://stackoverflow.com/posts/5702431/edit) – Dr. belisarius Apr 18 '11 at 11:56

2 Answers2

7

Yes. Look at RecurrenceTable. One also can program to define a function by its recurrence equation, factorial being the simplest example.

In[94]:= fac[1] = 1;
fac[k_Integer?Positive] := k*fac[k - 1]

In[96]:= fac[10]

Out[96]= 3628800

In[97]:= Function[If[#1 == 1, 1, #1*#0[#1 - 1]]][10]

Out[97]= 3628800

In[100]:= RecurrenceTable[
 f[k] == k f[k - 1] && f[1] == 1, f, {k, 1, 10}]

Out[100]= {1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800}
Sasha
  • 5,935
  • 1
  • 25
  • 33
  • 1
    @malina, the second example that Sasha gives is a pure recursive function, and they look distinctly odd the first several times you see them. Leonid talks about them a bit more in depth in this [answer](http://stackoverflow.com/questions/4198961/what-is-in-your-mathematica-tool-bag/4923345#4923345). – rcollyer Apr 18 '11 at 12:28
  • @rcollyer @Sasha I fail to see the point in the question (I commented about that there), and also in the answer. The three formulations are the same (as I see it), as you may convert from one to the other. So ... what is the question trying to find out? Just curious ... – Dr. belisarius Apr 18 '11 at 12:42
  • @belisarius I guess @malina was looking for an example that defines a function by its recurrence equation, and this is what the answer provided. I should have probably provided more educational links. I agree, neither the question nor the answer are particularly useful for the community at large being too basic. – Sasha Apr 18 '11 at 12:51
  • @belisarius, I agree to some extent; I was just trying to provide more insight into a confusing bit of notation. But, I disagree that the three examples are the same. While they are capable of giving the same result, they do so via different notations and `RecurrenceTable` may operate very differently than the others. On that alone, the answer is useful; the question, however, I don't know. – rcollyer Apr 18 '11 at 13:11
1

I wondered for a moment what RecurrenceTable is good for, until I rewrote Sasha's example using NestList:

Rest@NestList[{1, 0} + First@# {1, Last@#} &, {1, 1}, 10][[All, -1]]

{1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800}

If the involvement of k (First@#) is complicated, RecurrenceTable could be far simpler.

Bobby Treat
  • 101
  • 2