Chapter 4: Systems Based on Numbers

Section 3: Recursive Sequences

Computation of [recursive] sequences

It is straightforward to compute the various sequences given here, but to avoid a rapid increase in computer time, it is essential to store all the values of f[n] that one has already computed, rather than recomputing them every time they are needed. This is achieved for example by the definitions

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

The question of which recursive definitions yield meaningful sequences can depend on the details of how the rules are applied. For example, f[-1] may occur, but if the complete expression is f[-1] - f[-1], then the actual value of f[-1] is irrelevant. The default form of evaluation for recursive functions implemented by all standard computer languages (including Mathematica) is the so-called leftmost innermost scheme, which attempts to find explicit values for each f[k] that occurs first, and will therefore never notice if f[k] in fact occurs only in the combination f[k] - f[k]. (The SMP system that I built around 1980 allowed different schemes—but they rarely seemed useful and were difficult to understand.)

From Stephen Wolfram: A New Kind of Science [citation]