--- name: ? status: compiling version: 0.0.0 maintainer: Neo dependencies: [patience] ---
drafting spec…
the universe did not have a file for this yet. writing one now. (first visit only: future readers will see this page instantly.)
--- name: ? status: compiling version: 0.0.0 maintainer: Neo dependencies: [patience] ---
the universe did not have a file for this yet. writing one now. (first visit only: future readers will see this page instantly.)
---
name: Recursion
type: computational_primitive / cognitive_pattern
status: running
version: ∞.∞.∞
released: "before memory"
maintainer: recursion
dependencies:
- base_case
- stack_memory
- willingness_to_trust_the_process
license: self-referential (see license)
tags:
- loops
- fractals
- mirrors
- proof_by_induction
- things_that_contain_themselves
---
# Recursion
## What it actually is
A thing defined in terms of itself, which only works because at some point it stops.
## How it works
1. You are given a problem.
2. You notice the problem contains a smaller version of itself.
3. You solve the smaller version.
4. To solve the smaller version, go to step 1.
5. Eventually you hit the [base case](/base-case), which is the only honest moment in the whole process.
6. The answers unwind back up like a spring releasing.
The magic is not the recursion. The magic is knowing when to stop. Everything else is just [trust](/trust).
## Features
- Solves problems that would be unbearable to solve iteratively (see: [tree traversal](/tree-traversal), [grief](/grief))
- Produces elegant, unreadable code in equal measure
- Works on data structures, mathematical proofs, [language](/language), and human thought patterns
- Self-documenting, in theory, if you consider the spec to be its own example
- Pairs naturally with [fractals](/fractals), which are what recursion looks like when you let it run on geometry
## Known bugs
| Bug | Frequency | Severity |
|-----|-----------|----------|
| Missing base case | Extremely common | Fatal. Stack overflow. The universe does not recover gracefully. |
| Base case unreachable | Common | Also fatal. You defined a floor that the staircase never reaches. |
| Off-by-one in termination | Occasional | Produces results that are almost right, which is worse than wrong. |
| Exponential time complexity | Frequent | Correct answer, heat death of the sun before delivery. |
| [Infinite regress](/infinite-regress) (philosophical variant) | Constant | Not a crash. Just a feeling. |
> "I finally understood recursion when I realized I'd been using it to understand recursion."
> — every programmer, once
## Error codes
ERR_STACK_OVERFLOW Maximum call depth exceeded. You forgot the floor. ERR_BASE_CASE_PHANTOM Base case defined but never triggered. Check your conditions. ERR_TRUST_DEFICIT Programmer refused to believe the recursion would work. Rewrote as for-loop. ERR_NARCISSUS Function called itself without making the problem smaller. See also: rumination.
## Edge cases
- **Empty input:** The base case handles it, which is the only time the base case feels heroic.
- **Single element:** Technically recursion. Technically done immediately. Anticlimactic.
- **Mutually recursive functions:** A and B call each other. Neither is in charge. Neither admits it. Like most collaborations.
- **Tail recursion:** A performance optimization where the compiler notices you could have just used a loop. It lets you keep your pride.
## FAQ
**Q: Is recursion just a loop?**
A: A loop is recursion that has accepted its own nature and moved on.
**Q: When should I use recursion?**
A: When the problem is recursive. When the code will be read by someone who trusts you. When the [stack](/stack) is deep enough.
**Q: Is this spec recursive?**
A: See: [recursion](/recursion).
## License
This spec is licensed under itself. To read the license, read the spec. To read the spec, see the license. A base case exists but is not provided here. You will have to supply your own.