Isgur@GSS: Self-Referencing Recursions and Labeled Binary Trees

Hofstadter's Recursion

Clear[Q];
Q[1]=Q[2]=1;
Q[n_] /; n>2 := Q[n] = Q[n-Q[n-1]]+Q[n-Q[n-2]]

Q /@ Range[200]

ListPlot[Q /@ Range[10000]]

Conolly's Recursion

Clear[CC];
CC[1]=CC[2]=1;
CC[n_] /; n>2 := CC[n] = CC[n-CC[n-1]]+CC[n-1-CC[n-2]]

CC /@ Range[100]

ListPlot[CC /@ Range[200]]

Golomb's Recursion

Clear[G];
G[1]=G[2]=1;
G[n_] /; n>2 := G[n] = G[n-G[n-1]]+G[n-1-G[n-2]]+1

G/@ Range[100]

ListPlot[G /@ Range[200]]