Understanding recursion and role of replacement rule for recursion in Mathematica

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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])}} *)