4 ms·

i think the problem is that most people try to follow the recursions in their head which is hard. the biggest lesson regarding recursion is that if you're luck

by a-dub 4y ago

i think the problem is that most people try to follow the recursions in their head which is hard. the biggest lesson regarding recursion is that if you're lucky enough to have your problem fit with tco (or have guarantees your problem is small enough), it's actually way simpler to both write and verify. write the base case, write the inductive step, translate to code, done. no hard reasoning about the code required because math. fact and fib demonstrate this nicely. would prefer if programming languages offered a recursive decorator that would cause compilation or linting failures if tco isn't possible though.

DeathArrow 4y ago
>i think the problem is that most people try to follow the recursions in their head which is hard. It's hard for computers, too as it can easy result in stack overflow if there are too many steps.
- a-dub 4y ago
  that's the obvious issue. another less intuitive one is that modern cpus and compilers are essentially optimized for iterative algorithms. state variables can be kept in registers, simd can be used for data that appears in contiguous arrays, caching is built on locality assumptions and data locality is preserved. non-flattened recursive algorithms spread their state across linear memory with a full stack frame for every iteration. at the least this defeats gains from caches, at worst it defeats them entirely by filling them with junk. but, if the problem is small enough it can be worth it for the correctness guarantees and increased simplicity. trivial iterative algorithms are simpler, sure, but when things get more complicated, recursion can replace very hard to understand, test and debug iterative code with simple recursive definitions where guarantees of correctness and termination come for free.
  - Akronymus 4y ago
    If you go with a continuous passing style (which more often than not is relatively "easy") the compiler usually optimize it to replacing/reusing the frame rather than allocating a new one.
    - a-dub 4y ago
      so it turns out that optimization is also tco (tail call optimization). that said, i was previously unfamiliar with continuous passing style, thanks!

by a-dub 4y ago

DeathArrow 4y ago

>i think the problem is that most people try to follow the recursions in their head which is hard. It's hard for computers, too as it can easy result in stack overflow if there are too many steps.

a-dub 4y ago
that's the obvious issue. another less intuitive one is that modern cpus and compilers are essentially optimized for iterative algorithms. state variables can be kept in registers, simd can be used for data that appears in contiguous arrays, caching is built on locality assumptions and data locality is preserved. non-flattened recursive algorithms spread their state across linear memory with a full stack frame for every iteration. at the least this defeats gains from caches, at worst it defeats them entirely by filling them with junk. but, if the problem is small enough it can be worth it for the correctness guarantees and increased simplicity. trivial iterative algorithms are simpler, sure, but when things get more complicated, recursion can replace very hard to understand, test and debug iterative code with simple recursive definitions where guarantees of correctness and termination come for free.
- Akronymus 4y ago
  If you go with a continuous passing style (which more often than not is relatively "easy") the compiler usually optimize it to replacing/reusing the frame rather than allocating a new one.
  - a-dub 4y ago
    so it turns out that optimization is also tco (tail call optimization). that said, i was previously unfamiliar with continuous passing style, thanks!