3 ms·
> It’s also astonishing to me that people in a position to explain even moderately complex computing ideas continue to treat recursion as somehow hard to reason
by FeepingCreature 6y ago
> It’s also astonishing to me that people in a position to explain even moderately complex computing ideas continue to treat recursion as somehow hard to reason about. It’s calling a function.
Calling a function can be easily, and incorrectly, modeled by representing the arguments as variables stored at a fixed position in memory. (As function calls used to work.) Once you introduce recursion, this model breaks down and you are forced to think in terms of activation records/stackframes.
Probably those people learnt function calls in the former way first, meaning that recursion represented a conceptual leap for them.
- eyelidlessness 6y agoMaybe it’s more of me showing my naivety but I still think of a recursive function call as bindings and computation. My mental model is f(x) -> f(y(x)) = f(x) -> g(x), where g is a function wrapping the body of f. It’s surely not what the compiler does, but it makes thinking about recursion no more complicated than thinking about any old function. Then the only thing I need to think about beyond that is “does my environment support TCO, or am I certain my data fits in the call stack?”
- manwe150 6y agoConsider that some processors were too small to fit a stack. Some languages (notably BASIC), only had what you might call 'static' variables (to use the C name), so when you recursed into them, the variables would be shared across all calls to that function.
- eyelidlessness 6y agoAnd that’s a good case for supporting recursion but eliminating branching! You can goto and rebind to your heart’s content as long as you don’t have to back out of a condition
- mcguire 6y agoOr expressions.