Hoffstadter's Q sequence

Question

I am trying to understand Hoffstadter's Q sequence. I am suppose write a program that runs an equation that takes a positve integer from user input and outputs its corresponding Q sequence number. With a sample input of "5". The equation is "Q(n - Q(n - 1))+ Q(n - Q(n - 2))". The sample answer is "3". It is explained as:
Q(5 - Q(5 - 1))+ Q(5 - Q(5 - 2)) becomes Q(5 - Q(4))+ Q(5 - Q(3)) and then Q(5 - 3) + Q(5 - 2) and then Q(2) + Q(3) and finally, 1 + 2 = 3. Can anyone explain how Q(4) = 3, Q(3) = 2. If someone if write out how to get the numbers the sample out produced with this sequence, that would be great. Not asking for solution to the programming issue, but an explanation how the numbers mentioned are obtained. I startted running the Q numbers through formula but its like "what came first, the chicken or the egg". Much appreciated if anyone can help!

Answer 1

Q function is recursive and it calls itself in its definition.
Q(1) and Q(2) are defined as equal to 1 (Just like Fibonacci sequence)

Here is a brief of how Q(5) = 3:
Q(5 - Q(5 - 1))+ Q(5 - Q(5 - 2))
Q(5 - Q(4)) + Q(5 - Q(3))

calling Q(4)

Q(4 - Q(4 - 1))+ Q(4 - Q(4 - 2))
Q(4 - Q(3))+ Q(4 - Q(2)) # Q(2) = 1,
Q(4 - Q(3))+ Q(3)

calling Q(3)

Q(3 - Q(3 - 1))+ Q(3 - Q(3 - 2))
Q(3 - Q(2)) + Q(3 - Q(1))
# Q(2) and Q(1) = 1
Q(2) + Q(2)
2 # so Q(3) = 2

return 2 to Q(4)
Q(4 - 2)+ 2 # as Q(3) = 2
Q(2)+2
3 # so Q(4) = 3

return 3 to Q(5)

Q(5 - 3) + Q(5 - 2) # as Q(4) = 3 and Q(3) = 2
Q(2)+Q(3)
1+2 = 3
#so 3 is our answer

Regarding making it work in Python.... This could be done recursively quite easily with just 4 lines of code: (function with one if statement and two returns)

Answer 2

Aleksei Radchenkov,

Thanks for the very thorough explanation. My head is still spinning from the whole process, but at least now, I have a better understanding of how the sequence formula works. Again, thanks!