Comment by thaumasiotes 2 days ago
You should try playing with one of the toys. It's not at all difficult to move 7 of them.
It's not necessary to use a stack. If you have a goal, you can work "top down", with nothing held in memory. All you need to know to begin the move is whether you're moving an odd number of discs (in which case, the first move will be onto the target peg) or an even number (in which case it will be onto the third peg).
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?
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).