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 Hnn 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 an < 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.

One thought on “Recurrence relations and Python

  1. In C++ std::exchange has similar functionality so now it’s possible to do some cool tricks. Here is Fibonacci number calculation

    int fibonacci(int n)
    {
         auto b=1;
         for (auto a=1; --n; a=std::exchange(b,a+b));        
         return b;    
    }
    

    Here is a code that calculates tribonacci numbers:

    int tribonacci(int n)
    {
        int t0=2, t1=1, t2=1;
        for (; n; t2+=exchange(t0, exchange(t1, t2)) + t0, n--);
        return t0;
    }
    

Leave a Reply

Your email address will not be published.