[Solved] Solution of code coach [Hofstadter's Q-Sequence]

Question

What's wrong with this code:
It passed only 2 cases
def q_sequence(n):
if n == 1 or n == 2:
return 1
else:
return q_sequence(n - q_sequence(n - 1)) + q_sequence(n - q_sequence(n - 2))
How can I fix this ?
Thanks in advance.

def main():
n = int(input(" "))
if n <= 0:
print("Please enter a positive integer.")
else:
result = q_sequence(n)
print( result)

if __name__ == "__main__":
main()

Answer 1

I would say your code runs only for n <= 35 (more or less) after that you run into a stackoverflow.

https://en.m.wikipedia.org/wiki/Stack_overflow#:~:text=The%20most%2Dcommon%20cause%20of,can%20fit%20on%20the%20stack.

You can try an iterative solution (using for or while loops) or you can try recursion with memoization.

https://wellsr.com/JUMP_LINK__&&__python__&&__JUMP_LINK/optimizing-recursive-functions-with-python-memoization/

Answer 2

piano T thanks for your efforts
It has passed 5 caese but not passing 6 case

def q_sequence(n, cache={1: 1, 2: 1}):
if n not in cache:
cache[n] = q_sequence(n - q_sequence(n - 1, cache), cache) + q_sequence(n - q_sequence(n - 2, cache), cache)
return cache[n]

def main():
n = int(input(" "))
if n <= 0:
print("Please enter a positive integer.")
else:
result = q_sequence(n)
print(result)

if __name__ == "__main__":
main()

Answer 3

This code has only passed two cases, the 1st and the 2nd. The remaining four cases are failing.

Answer 4

I know where the case test 6 problem comes from The programme starts with the first two known values in the sequence. It then uses a loop to build each subsequent value sequentially. This method only works with results that have already been calculated, which greatly simplifies the understanding and maintenance of the code. It completely eliminates any risk of stack overflow due to deep recursion. By calculating the values linearly programme execution time is considerably reduced as the same information does not have to be recalculated several times.

thanks for your help Denise Roßberg

Here's the method in the code: def q_sequence(n):
cache = {1: 1, 2: 1}
for i in range(3, n+1):
q_n_minus_1 = cache[i-1]
q_n_minus_2 = cache[i-2]
index_1 = i - q_n_minus_1
index_2 = i - q_n_minus_2
if index_1 <= 0 or index_2 <= 0:
continue
if index_1 in cache and index_2 in cache:
cache[i] = cache[index_1] + cache[index_2]
else:
continue

return cache.get(n, "No valid value for this n")

Answer 5

You can implement memoization a technique that stores the results of recursive function calls in a cache so they do not have to be recalculated every time. It might work but I'm not sure

def q_sequence(n, cache={1: 1, 2: 1}):
if n not in cache:
cache[n] = q_sequence(n - q_sequence(n - 1, cache), cache) + q_sequence(n - q_sequence(n - 2, cache), cache)
return cache[n]

Answer 6

Another method is to set the recursion limit.

import sys
sys.setrecursionlimit(2000) # 2000 for example, you can set it higher or lower

However, memoization runs much faster since it doesn't need to re-calculate again.

Answer 7

I have solved it, here is the updated version

from sys import setrecursionlimit
setrecursionlimit(100000)

results = [0] * 10000

def Q(n):
if n < 1:
return
if n <=2:
return 1
if results[n] != 0:
return results[n]

results[n] = Q(n - Q(n - 1)) + Q(n - Q(n -2))

return results[n]

x = int(input())

print(Q(x))

And thank you all for your efforts

Answer 8

I’ll have to look up what a Q sequence is, but right off the bat, it’s extremely risky having a function call itself like you do here. You should always avoid that if possible.

Answer 9

I have looked up the Q sequence. It looks like function recursion is the easiest way to do it, and it also looks like you’ve done it correctly. The first 20 terms of the function you wrote match the 20 terms listed on Wikipedia, and as far as I can tell, the formula is correct. What cases did it fail? Did the code coach give a reason why?

Answer 10

I don’t know what the other two cases are.