Hofstadter's Q -Sequence ?

Question

I am getting bizarre results with what seems like an easy program to write. For n>35, I *usually* get “no output,” though sometimes it will correctly give me the answer, eg 19 for n=36. Is this a memory issue—or is there some limit on recursion I’m not grasping?

https://code.sololearn.com/czp6KDt3yw7r/?ref=app

Answer 1

Yes, it might be a time issue since the program has a limited time frame to execute. Try using some means of caching results (memoization) to cut the number of recursions.

Answer 2

JRS Actually in Python or C# we can use dictionary based objects which make the task easier

Answer 3

Bob_Li thank you

Answer 4

It's probably a timeout issue. Sololearn times out pretty quickly. Have you tried running the code somewhere else?

Answer 5

Not dumb. Awareness for the efficiency of an algorithm is important. Now try to make it work for any n >70 and find the next limit...

Answer 6

Simon Sauter It can be solved. It just has to be solved without using recursion.

Answer 7

JRS Try using an array, and populate it sequentially. Then get the value of the last populated array element.

Answer 8

JRS
If all else fails, Google is your friend.
Here is a solution that works and passes the challenge.
It basically just precomputes the array, then you just find the answer by it's index.
The sequence may be hard to predict, but easy to simulate.
Directly computing the answer is computationaly expensive for large values, but the sequence is relatively easy to generate without using recursion.

https://code.sololearn.com/c8ZnDtoL15Xp/?ref=app

Answer 9

JRS
It is not a Sololearn problem, it's just the nature of recursive functions... they blow up.
You just have to find another way,

Answer 10

can i get the problem statement?

Answer 11

Harsha S
It's a code coach challenge.

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

Answer 12

So in the real world, should recursive functions be avoided?

Answer 13

JRS The problem with those recursive functions is that they create an overflow on the stack.

Answer 14

Hmm, okay, I will try that, thanks!

Answer 15

Right, but try 37. Or 50.

Answer 16

I just tried using an array with the first 70 q values…works fine for n<=70. So it is a timing issue I guess. Dumb.

Answer 17

I meant it’s dumb that sololearn works that way. This is a code challenge for those of us who are beginners—and I did have the code correct, but couldn’t pass the challenge because their program can’t be bothered to wait another half a second or whatever. Seems silly that their code-checking software returns a false negative. That’s all.

Answer 18

I understand :)

Answer 19

If this is a sololearn code challenge and it can't be solved because of this you can send a bug report to [e-mail].

Answer 20

JRS
if it results in problems like this, yes.