Finding Hofstadter's Q-Sequence very slow

Question

I'm trying to find Hofstadter's Q-Sequence.

I tried:

RSolve[{Q[n] == Q[n - Q[n - 1]] + Q[n - Q[n - 2]], Q[1] == 1, Q[2] == 1}, Q[n], n]

but it doesn't work.

Then I tried:

Q[1] := 1
Q[2] := 1
Q[n_] := Q[n - Q[n - 1]] + Q[n - Q[n - 2]]

Table[Q[n], {n, 15}]

{1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, 8, 8, 8, 10}

but it works very slowly.

I want to plot first 200 terms of Q-Sequence but there is no answer...

ListPlot[Table[Q[n]/n, {n, 200}]]

Answer 1

Proper memoization is the key:

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

data = Table[Q[n]/n, {n, 10000}]; // AbsoluteTiming

{0.051379, Null}

ListPlot[data]