Ok, confession time: every once in a while, you find out something that apparently everyone except for you knows about (I’m looking at you, pronunciation-of-rendezvous). This time, I totally missed out on recursion in the course of teaching myself how to program. For those in the same boat as me, this means you can call a function inside the same function. So long as you specify a base case (and make sure you reach this base case), you can get a reasonable answer.
In the course of rectifying this, I’ve written two toy programs. The first is very un-mathy, but essentially solves the game “TextTwist“. First I use recursion to find all possible substrings of a collection of letters, then I import an English dictionary (thank you, Python!), and check these substrings against the dictionary to come up with a list of English-language words. See below for the print-out.
The second program I wrote was in MATLAB, and the code is a little cleaner, so I can in fact post it here. It uses recursion to again generate the Sierpinski gasket from the flurry of fractal posts I had earlier, though this is a deterministic approach. What it does is takes a column of points determining the vertices of a triangle (or any other shape), then for each point, returns a column determining the points of a triangle whose vertices are halfway to the previous vertex, and halfway to the next vertex. The code may be easier to read, noticing especially that I call gasket on the third to last line:
function [A,B] = gasket(X,Y,N)
%returns the coordinates of the vertices for a Sierpinski gasket with N
m = size(X,1)-1;
A = ;
B = ;
for k = 1:m-1
A = [A,[X(cmod(k,m),:);(X(cmod(k+1,m),:)+X(cmod(k,m),:))/2;(X(cmod(k-1,m),:)+X(cmod(k,m),:))/2;X(cmod(k,m),:)]];
B = [B,[Y(cmod(k,m),:);(Y(cmod(k+1,m),:)+Y(cmod(k,m),:))/2;(Y(cmod(k-1,m),:)+Y(cmod(k,m),:))/2;Y(cmod(k,m),:)]];
[A,B] = gasket(A,B,N-1);
The function “cmod” just changes the “mod” function so that “cmod(m,m) = m” instead of the usual behavior where “mod(m,m) = 1″. Running this code with N = 8, we get the following image:
Noticeably cleaner than at least some of the randomly generated fractals from earlier, and at the very least faster. After 8 iterations, there are 3^8 = 6561 triangles, and for each we store 4 pairs of numbers to generate a triangle (I am calling the “line” command, which means I need to specify that the start and end points are the same), so the total number of numbers I store is 52,488, compared to 100,000 for this much lower resolution version from earlier. Also, I can start with any set of points I want with this program, so here is a belated Valentine for everyone: