Recurrence relations and Python
A video by Raymond Hettinger points out that simultaneous assignment makes it much easier to understand code that evaluates a recurrence relation. His examples were in Python, but the same principle applies to any language supporting simultaneous evaluation.
The simplest example of simultaneous evaluation is swapping two variables:
a, b = b, a
Compare this to
temp = a a = b b = temp
The latter is more code, but more importantly it exposes intermediate steps that could be confusing if the code were more complicated. This is the case when evaluating recurrence relations.
The most famous recurrence relation is the Fibonacci sequence, but I'll use a difference example because Fibonacci is overdone. Also, I think it helps to see a slightly more complicated example.
As I wrote earlier here, the first two Hermite polynomials are given by H0(x) = 1 and H1(x) = x. The rest are given via the recurrence relation
Hn+1(x) = x Hn - n Hn-1(x).
If we have a particular value of x, say x = 3, and we want to find H10(x) we could do so as follows.
x = 3 a, b = 1, x for n in range(2, 11): a, b = b, x*b - n*a
After this code runs, b will contain H10(3). [1]
At each iteration, the calculations on the right side of the equal sign are carried out, then the assignments to the elements on the left side are made. You don't have to write explicit and confusing code with variables like a_old and a_new.
Three-term recurrence relations come up constantly in application. For example, all orthogonal polynomials satisfy some three-term recurrence analogous to the one given above for Hermite polynomials.
Power series solutions for differential equations lead to recurrence relations for the coefficients. Second order ODEs give rise to three-term recurrence relations. In general nth order ODEs give rise to n+1 term relations. By far the most common value of n in application is 2, but higher values come up occasionally.
A third-order ODE that leads to a four-term recurrence could be implemented in Python with code of the form
a, b, c = b, c, f(a,b,c)
See this post for an example of a recently discovered three-term recurrence relation.
One final comment on recurrence relations: recurrences that hold in theory may not be useful in practice. Repeated evaluation of a recurrence might have problems with numerical stability. That's the topic for the next post.
***
[1] If you're not used to Python's range generator, you might be surprised that the second argument is 11 rather than 10. This is because range(a,b) uses half-open intervals, i.e. it generates values n with a a n < b. This has its advantages. For example, it composes well under unions: the union of range(a,b) and range(b,c) is range(a,c). This wouldn't be the case if range returns its upper limit.