Comment by GrayShade
Yes, I'm aware of the iterative solution, which is why I explicitly mentioned the recursive one.
They tried to give the algorithm description to the LLMs, but they also used the recursive solution (see page 25 of the paper).
Yes, I'm aware of the iterative solution, which is why I explicitly mentioned the recursive one.
They tried to give the algorithm description to the LLMs, but they also used the recursive solution (see page 25 of the paper).
What do you think a human using the recursive solution looks like?
If you ask someone how the puzzle works, they're overwhelmingly likely to tell you:
"To move disc 7, first you move discs 1-6 to the third peg, then you move disc 7[, and then you can put discs 1-6 back on top of it]."
This is an explicitly recursive statement of the solution. But the implementation is just that you count down from 7 to 1 while toggling which peg is "the third peg". You can optimize that further by dividing 7 by 2 and taking the remainder, but even if you don't do that, you're using constant space.
What would a human be doing (or thinking) differently, if they were using the recursive algorithm?