One of the most useful classes of function are those defined via a ``recurrence relation.'' A recurrence relation makes each successive recurrence relation value depend on some or all of the previous values. A simple example is the ordinary ``factorial'' function:
The value of depends on the value of , on , and so on. Because it depends on only one previous value, it is usually called a first order recurrence relation. You can easily imagine a function based on two, three or more previous values. The Fibonacci numbers are probably the most famous function defined by a Fibonacci numbers second order recurrence relation.
The library function fibonacci computes Fibonacci numbers. It is obviously optimized for speed.
Define the Fibonacci numbers ourselves using a piece-wise definition.
As defined, this recurrence relation is obviously doubly-recursive. To compute , we need to compute and . And to , we need to compute and . And so on. It seems that to compute we need to compute once, twice, three times. Look familiar? The number of function calls needed to compute any second order recurrence relation in the obvious way is exactly . These numbers grow! For example, if Axiom actually did this, then requires more than function calls. And, given all this, our definition of fib obviously could not be used to calculate the five-hundredth Fibonacci number.
Let's try it anyway.
Since this takes a short time to compute, it obviously didn't do as many as operations! By default, Axiom transforms any recurrence relation it recognizes into an iteration. Iterations are efficient. To compute the value of the -th term of a recurrence relation using an iteration requires only function calls. Note that if you compare the speed of our fib function to the library function, our version is still slower. This is because the library fibonaccifibonacciIntegerNumberTheoryFunctions uses a ``powering algorithm'' with a computing time proportional to to compute fibonacci(n).
To turn off this special recurrence relation compilation, issue set function recurrence
To turn it back on, substitute ``on'' for ``off''.
The transformations that Axiom uses for fib caches the last two values. For a more general -th order recurrence relation, Axiom caches the last values. If, after computing a value for fib, you ask for some larger value, Axiom picks up the cached values and continues computing from there. See ugUserFreeLocal for an example of a function definition that has this same behavior. Also see ugUserCache for a more general discussion of how you can cache function values.
Recurrence relations can be used for defining recurrence relations involving polynomials, rational functions, or anything you like. Here we compute the infinite stream of Legendre polynomials.
The Legendre polynomial of degree
The Legendre polynomial of degree
The Legendre polynomial of degree .
Compute the Legendre polynomial of degree