3 ms·
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
by GrayShade 1y ago
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).
- thaumasiotes 1y agoWhat 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?