Definition
Recursion (or nesting) is a mechanic in which a board containing another board of the same kind is itself the puzzle material. The player's verbs can stay ordinary — enter, push, carry. What changes each turn is not only where the pieces are but the shape of the nesting: which board, at which depth, is currently instantiated. The level is solved by reaching a goal, but the route to it crosses levels of depth.
Self-similarity is the key. The same rule holds however deep you look. The player therefore learns one rule, and the designer adds problems without adding rules. Depth multiplies rather than adds. It is an unusually efficient invention: a tiny vocabulary that makes the state space explode.
Origins and lineage
The earliest deliberate use of nesting as a puzzle is not digital but a toy. In 1883 the mathematician Édouard Lucas put the Tower of Hanoi on sale in Paris. Moving a tower of n discs splits into two copies of the same problem with n−1 discs, plus one move of the largest disc. The shortest solution satisfies T(n)=2·T(n−1)+1, which resolves to 2ⁿ−1. Two rules were enough to produce self-similarity.
An older lineage runs through ring puzzles. In the baguenaudier, freeing one ring first requires putting an earlier ring back, so the procedure folds back on itself. Both toys taught the idea of calling a smaller copy of yourself through the fingers rather than through words.
The best-known digital work to take recursion as its subject is Recursed by Portponky, released on Steam on 30 September 2016. Jump into a treasure chest and you enter the room inside it; carry the chest and you carry the room. Re-entering a chest restores its contents to their initial state. The design translates function calls and variable scope into the vocabulary of a jumping game. No single title can be fixed as the mechanic's first appearance, but this is the one cited again and again.
Variations
Patrick's Parabox by Patrick Traynor (29 March 2022) rebuilt the same nesting on top of Sokoban-style pushing. The only verb is push, yet inside the box you push there is another board. A box can be pushed into another box, and a box can even be pushed into itself. Where Recursed showed nesting as vertical entry and exit, this folds it into horizontal pushing.
COCOON by Geometric Interactive (29 September 2023) translates nesting into bodily sensation. The sphere on your back is a world, and carrying spheres rearranges how the worlds sit inside one another. Difficulty is kept low; the feeling of carrying a world matters more than the satisfaction of cracking a level. It shows that the mechanic need not aim at difficulty at all.
Maquette by Graceful Decay (2 March 2021) shows the inside and the outside at once rather than letting you descend. A small model on a plinth maps one-to-one onto the wide world around it, so a cube in your hand becomes a bridge outdoors. Few objects can be nested; recursion works here as a metaphor of scale, not as combinatorial depth. As the counter-reading of Maquette concludes, that narrow range is a choice rather than a fault.
Design pitfalls
The first pitfall is turning depth directly into difficulty. One more level of nesting sends the state space soaring. For Recursed, whose jars act as continuations, deciding whether a general level is solvable has been proven undecidable (Demaine, Kopinsky and Lynch, ISAAC 2020). The supply of problems is inexhaustible, but a human can hold only two or three levels of depth at once. Adding depth is easy; restraining it is the hard part.
The second is teaching the properties in the wrong order. Nesting, self-reference, infinite regress and inversion are separate ideas. Traynor separated them level by level. As he said in his GDC 2024 talk, levels exist to show the system rather than to make it harder. Present several properties at once and the player loses the words for what they do not yet understand.
The third is making failure illegible. When objects move across levels of depth, it is hard to see at which depth an irreversible move happened. As the essay on legible failure argues, the problem with a soft lock is not that it occurs but that the player cannot tell it has occurred. The unit of undo should be aligned with the unit of nesting.
How to tell it apart
The difference from impossible space is whether the repetition has depth. The world of Manifold Garden goes on forever, but the same space is tiled flat; there is no inside and outside. Recursion means A inside A, not A next to A.
Portals connect two distant points, but the far side need not contain the near one. Rule rewriting moves the rules themselves, whereas recursion keeps the rules fixed and adds depth to the board. Scale pieces such as Maquette are the easy confusion: if only the appearance changes it is a perspective trick, and if the large and the small exist as genuinely separate levels it is recursion.
Further reading
On this site. The overview of the mechanic is Making recursion playable: the nesting grammar of Patrick's Parabox and Recursed. For the designer, see the philosophy of Patrick Traynor; for nesting applied to verbs themselves, Andrew Plotkin on verbs made of verbs. For history, Tower of Hanoi (1883). From the music side, the soundtrack of Patrick's Parabox and the soundtrack of COCOON. For a critical reading, the counter-reading of COCOON; for the view from someone who cannot solve it, watching Aliensrock play Patrick's Parabox.
Primary sources elsewhere. Erik D. Demaine, Justin Kopinsky and Jayson Lynch, "Recursed is not Recursive: A Jarring Result" (ISAAC 2020), proves that Recursed with jars is RE-complete by reduction from the Post Correspondence Problem, and builds the levels within the game's real 15 × 20 room size. For the facts on the Hanoi toy, Wikipedia: Tower of Hanoi.
桌面形态
- Tower of Hanoi (1883) — moving a tower of n discs decomposes into two copies of the same problem with n−1 discs. Three pegs and a few wooden discs embody recursion itself.
- Baguenaudier (Chinese rings) — to free one ring you must first put an earlier ring back. The solving procedure folds back into itself, step after step.
相邻机制
Sokoban-style Pushing / Impossible Space / Portals / Perspective Tricks / Rule Rewriting
