Hofstadter's Q sequence

Question

"""Hofstadter's Q-Sequence is a sequence of numbers where every integer above zero has a corresponding q-sequence value.
You can determine the q-sequence value from a formula that tells you how far back in the sequence to go and add two values together.
The first two values of the sequence are Q(1) = 1 and Q(2) = 1, and every number above 2 can be expressed according to the following formula (n is your input): Q(n) = Q(n - Q(n - 1)) + Q(n - Q(n -2))

Task:
Given an integer value input, determine and output the corresponding q-sequence value."""

a = int(input())

def hof(n):
if n <=1:
return 1
elif n ==2:
return 1
elif n==3:
return 2
elif n==4:
return 3
elif n==5:
return 3
else :
return hof(n - hof(n - 1)) + hof(n - hof(n - 2))

print(hof(a))

# To this question, the code lines above do not produce the expected result. I am not sure where it went wrong. if anyone would help me I would appreciate it. Thanks in advance!

Answer 1

For input 30, it recursive calls are above 900000 +
Anything above, it's cause sololearn time out...

I think, you can do this by memorization.. the way you wrote for case 3,4,5 , store it in datatypes.. and use instead for repeated calls..

You're welcome..

Answer 2

Is that working?
You are hard coding for cases 3 to 5 , it may return less or more in recursive calling I think. According to description and your solution, I think that may be the problem I guess. Because all other seems fine.. what is your expected output for a sample input. .?

Answer 3

Remove cases 3 to 5 , and try then...

Answer 4

Thanks for such fast response, but I do not understand your answer. Would you elaborate on it if you like?

Answer 5

It works perfectly fine on laptop so maybe on phone, it took too long to give an output, if input becomes too big to process. e.g. on phone, up to input 40, it works; yet from input 50, it took forever and returned no output. But on laptop it works just fine. Anyway many thanks for your answer, much appreciated!

Answer 6

n = int(input())

q_list = [[1,1],[2,1]]

def hofstadter(x):
global q_list
for i in range(len(q_list)):
if x == q_list[i][0]:
return q_list[i][1]
return hofstadter(x - hofstadter(x - 1)) + hofstadter(x - hofstadter(x -2))

def add_q(x):
global q_list
for i in range(1,x):
q_list.append([i, hofstadter(i)])

add_q(n)

print(hofstadter(n))