Recursive Structure of Hofstadter Sequences

I'm slowly (but surely!) making my way through Godel, Escher, Bach: An Eternal Golden Braid by Douglas Hofstadter. As I've mentioned before, so far it's been quite an awesome, thought-provoking read; exploring some pretty deep ideas from both mathematics and computer science.

One of those deep ideas is that of recursion. Upon introducing the idea with an amusing "story within a story within a story" dialogue, we are shown several peculiar sequences: starting with the G(n), H(n), F(n) and M(n) sequences. These are examples of Hofstadter sequences. The trick to these sequences is not only that they are recursively defined, but that they are, in fact, non-linearly recursive. G and H are both defined in terms of compositions of themselves. Even more strangely, F and M are defined in terms of nested compositions of each other!

The exercise that Hofstadter gives the reader is to determine the recursive structures that can be created by forming a graph of each of the sequences: where we label some nodes '1' through 'n', and let 'n' be the node directly above the node 'G(n)' in the graph. As we'll see, the graphs branch up and out like a tree, and we'll be able to notice some recursive patterns that define the infinite construction of the entire graph.

So let's get to it! To save having to calculate the values of the sequence by hand, we'll code up some recursive functions in Clojure that we can use to easily find the values for each of the Hofstadter sequences.

The N-Queens Puzzle and Recursion

One of the cooler exercises from the Structure and Interpretation of Computer Programs is Exercise 2.42: finding solutions to the N-Queens Puzzle.

The N-Queens Puzzle is a sort of chess puzzle. Suppose we have an NxN chessboard, and N queen pieces. We want to find a way to position the pieces so that none of the queens can capture each other. In fact, we want to find all possible ways to do this.

Over the next couple of blog posts, we'll consider two techniques for getting a grasp on this puzzle:

• Today, we'll look at a recursive method that constructs the set of all feasible solutions by building them up a column at a time, which we'll implement using Clojure.
• In the next post, we'll see how we can formulate the N-Queens puzzle as a 0-1 Integer Linear Program (ILP), which we can solve using Java in conjunction with some open source operations research tools; namely the SCPSolver with the GNU Linear Programming Kit (GLPK).

4 Ways to Generate the Fibonacci Numbers

In keeping with our recent theme of generating famous number structures, we'll consider the Fibonacci sequence today. This post was also inspired by some of the examples and exercises in the Structure and Interpretation of Computer Programs (namely Exercise 1.13 and Exercise 1.19 for those that came for the Scheme solutions.)

The story goes that the Fibonacci numbers were so named by the Italian mathematician Leonardo Fibonacci in the 1200's, when he discovered the sequence while forming a mathematical model for rabbit populations. However evidence suggests that the sequence was known to others before then (it seems to appear in earlier Indian mathematics, for instance.)

The Fibonacci numbers also have an interesting relationship with the Golden Ratio, namely that as we take larger and larger numbers in the sequence, the ratio between one number and the next approaches the Golden Ratio.

Or mathematically:

And these numbers pop up in all sorts of places. Remember Pascal's triangle? Turns out if you draw some “shallow diagonal” lines across the triangle and sum up the numbers on each line, you get the Fibonacci sequence too!

(There's a nice picture of this here.)

Though that history is all well and good, computation is always much more interesting! We'll look at four different ways to generate the Fibonacci numbers, with Clojure taking centre stage as our JVM language today, including some guest appearances from Python (or Jython if you like, so as to keep with the JVM theme.)

Computing Pascal's Triangle

One of the coolest things about the Structure and Interpretation of Computer Programs has to be the exercises, in my view. Some of them are surprisingly deep explorations of mathematical or computational ideas, and even the ones that aren't still end up being quite interesting.

As the first real post for this blog, I figured I'd start off with one of the exercises in that latter category: not as deep, but still pretty cool. This exercise involves computing the numbers of Pascal's Triangle.

[For those that are interested, in the book we're dealing with Exercise 1.12 here. My worked solution in Scheme is available in my GitHub repository. However, in this post I'll be going wild with this exercise and looking at the problem for all sorts of weird angles (and all of the code will be in the JVM languages to keep with the blog's theme.) So the Scheme solutions are still worth a look if you've read this post, and vice versa.]