Understanding recursion and role of replacement rule for recursion in Mathematica

From the book "Essentials of Programming in Mathematica" (Fibonacci numbers):

If we think of this sequence as a function, we would just change this to a functional definition.

F(1) = 1
F(2) = 1
F(n) = F(n – 2) + F(n – 1), for n > 2

In this form, we can translate the definition directly into code. The condition n > 2 is unnecessary because specific rules such as F[1] = 1 are looked up before more general rules like that for F[n].

F[1] = 1;
F[2] = 1;
F[n_] := F[n - 2] + F[n - 1]


Questions

1. What do F[1] = 1; and F[2] = 1; mean, and what they do? For me, it looks like we are calling the function that is not even defined yet and assigning it a value. I do not understand that.

2. How F[n_] := F[n - 2] + F[n - 1] and F[1] = 1; and F[2] = 1; are related to each other and how they influence each other?

3. Is there is another, better example to understand recursion in Mathematica?

• Please read a documentation page ref/Set. f[1]= is mentioned in Details section as well as e.g. in Scope / lhs.
– Kuba
Commented Sep 25, 2018 at 7:01
• Those tutorials cover it even better: tutorial/MakingDefinitionsForFunctions, tutorial/MakingDefinitionsForIndexedObjects.
– Kuba
Commented Sep 25, 2018 at 7:04
• Possible duplicate of How to deal with recursion formula in Mathematica? Commented Sep 25, 2018 at 7:37
• @m_goldberg I think it is more "related" question than "duplicate". My question is more related to replacement rule role in recursion and the question you linked is more recursion in general type of question. But anyway it is nice to have the link you provided in my question. Commented Sep 25, 2018 at 8:13
• I agree that it is not a duplicate. To this question a good answer would cover DownValues and "everything is an expression".
– Johu
Commented Sep 25, 2018 at 9:16

Mathematica is a term-rewriting system. You can image it as a set of replacement rules and a main loop that recursively applies these replacements to an expression until none of the replacement rules matches. So, in this sense, the recursion is immanent to the language design.

Executing

F[1] = 1


adds the replacement rule HoldPattern[F[1]] :> 1 to the list of rules. (You can evaluate DownValues[F] to see which rules where attached to the symbol F.) From now on, whenever F[1] appears in an expression, Mathematica will replace it by 1.

Moreover,

F[n_] := F[n - 2] + F[n - 1]


does not define a "function" in the usual sense; it adds HoldPattern[F[n_]] :> F[n - 2] + F[n - 1] to the list of rules. But as this rule consists of a transformation, F behaves like a function from now on.

• 1. When we use the term "rule" in Mathematica, is it always means "transformation rule" or there are other kinds of rules too? 2. Does the last paragraph of your answer true for every other function in Mathematica too or it is true only in this particular example? If it is only true in this particular example please explain why. Commented Sep 25, 2018 at 7:52
• @vasili111 There are other tupes of functions in Mathematica, for example Function (also called "pure function"), CompiledFuntion (produced by Compile). Commented Sep 25, 2018 at 7:58
• @vasili111 Rules (see Rule) can also occur in the definition of Associations, Graphs, and SparseArrays or for specifying options. In this case, the term "transformation rule" might not be appropriate. Commented Sep 25, 2018 at 8:00
• So, just to summarize, my code in the question means: IF calling F as F[1] or as F[2] return 1. In other cases of calling F return result of F[n_] := F[n - 2] + F[n - 1]. Is it right? Commented Sep 25, 2018 at 8:57
• Yes. That's right. One has to know that Mathematica will always prefer a more special pattern over a more general one. F[1] evaluates to 1 (and does not start an infinite recursion) because the pattern F[1] is more special than F[n_]. Commented Sep 25, 2018 at 9:02

I think the question is coming from a different programming background of the OP:

What do F[1] = 1; and F[2] = 1; mean, and what they do? For me, it looks like we are calling the function that is not even defined yet and assigning it a value. I do not understand that.

As Mathematica isn't a compiled language (though technically this shouldn't preclude anything), it lets you update definitions multiple times. It's quite type-agnostic, so it doesn't need declaration either. What happens here is when you run F[1] = 1, the C-code equivalent would be

int F(int n) { // no need for "int" type specification in Mathematica
if (n == 1) return 1;
return F(n); // impossible in C, but simply returns unevaluated in Mathematica
}


When you then run F[2] = 1, the definition is immediately updated:

int F(int n) {
if (n == 1) return 1;
if (n == 2) return 1;
return F(n);
}


Finally F[n_] := F[n - 1] + F[n - 2] gives

int F(int n) {
if (n == 1) return 1;
if (n == 2) return 1;
if (n == anything) return F(n-1) + F(n-2);
return F(n);
}


Parting thought: Mathematica has a notion of specificity of patterns. If you evaluate in reverse

F[n_] := F[n-1] + F[n-2]
F[2] = 1
F[1] = 1


the equivalent C-code would be

int F(int n) {
if (n == 2) return 1;
if (n == 1) return 1;
if (n == anything) return F(n-1) + F(n-2);
return F(n);
}


I.e. the definitions for 1 and 2 are reversed, but the least-specific argument case goes to the end. This can, however, be overridden.

• Very good explanation. Thank you. Commented Sep 25, 2018 at 9:48
• "no need for "int" type specification in Mathematica" - indeed not needed, but it is useful to have argument checking like f[n_Integer] := (* stuff *). Commented Sep 25, 2018 at 13:26

The definitions for F[1] and F[2] are the initial (stopping) values for F. Without them, the recursion could not stop and would theoretically result in an infinite recursion (in practice stopped by value for $RecursionLimit). Clear[F] F[n_] := F[n - 2] + F[n - 1] F[5] (*$RecursionLimit::reclim2: Recursion depth of 1024 exceeded during evaluation of F[-2039-2].

Hold[F[5 - 2] + F[5 - 1]] *)


Consequently,

Clear[F]

F[1] = 1;
F[2] = 1;


For efficiency use memorization

F[n_Integer?Positive] := F[n] = F[n - 2] + F[n - 1];


For a fuller definition, rearrange the terms and use a change of variables to obtain

F[n_Integer?NonPositive] := F[n] = F[n + 2] - F[n + 1];

Show[Plot[Fibonacci[n], {n, -5.2, 5.2}],
DiscretePlot[F[n], {n, -5, 5}]]


For a complete definition, use RSolve

Clear[F]

RSolve[{F[n] == F[n - 2] + F[n - 1], F[1] == 1, F[2] == 1}, F[n], n]

(* {{F[n] -> Fibonacci[n]}} *)


The recursion without initial values does not uniquely define the result, i.e., different initial values will give different results.

Clear[F]

RSolve[{F[n] == F[n - 2] + F[n - 1], F[1] == 1, F[2] == 2}, F[n], n]

(* {{F[n] -> 1/2 (Fibonacci[n] + LucasL[n])}} *)

• Thank you. Very helpful answer. Commented Sep 26, 2018 at 14:42
• As a side note: Memorisation technique discribed above is also called "Dynamic programming". Also, Dynamic programming will entail some increased cost in memory, as the global rule base is expanded to include the new rules. Source, book: "Essentials of Programming in Mathematica", Chapter Dynamic programming. Commented Sep 26, 2018 at 15:32