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 (where n is your input value): 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.

Input Format:
A positive integer value.

Output Format:
A positive integer value that represents the value in the q-sequence that the input holds.

Sample Input:
5

Sample Output:
3

What is the error in my code ?

https://sololearn.com/compiler-playground/cHtkQCAH8GeX/?ref=app

Answer 1

Recursive functions might be simple to write, but it's a resource hog. For high values, it would eat up your resources before it can even begin the computation. As Jan and Wong Hei Ming suggested, modify your code to use iterative method, or add a cache or a limit to your recursion.

btw, for your recursive function, lru_cache was only useful for n<=499.

iterative computation seems to be the only way to get higher values.

It is unfortunate that only the recursive form was introduced in the challenge introduction. It might be easier to visualize, but it's the worst method to base your code on.

Answer 2

You have to solve it without using recursion, and you can do that by using a for loop and an array, and then it will pass all test cases. Just create the same pattern with the array as you did with the functions.

Answer 3

It looks fine to me... from what I've read, you might have a problem with a higher n value, e.g. 1000 times out.
What problem do you have? Is it a task on Sololearn?

Answer 4

Other options include using the lur_cache from the functools library, or set the recursion limit.