2 ms·
The divide-and-conquer algorithm is a subset of what the post calls generative recursion, which requires a non-trivial amount of logic to get it right (even the
by lifthrasiir 4y ago
The divide-and-conquer algorithm is a subset of what the post calls generative recursion, which requires a non-trivial amount of logic to get it right (even the simplest algorithm like binary search can be surprisingly difficult).
- layer8 4y agoAh, the post neglected to explain what they mean by generative recursion. The difficulties however are “just” in off-by-one errors and in the boundary cases of fixed-size integer types, which don’t get in the way if understanding the solution approach. You can easily understand it without having to understand recursive data structures. In that aspect, it shares the simplicity with fibonacci etc., but is more compelling than those because the alternative iterative solution is more difficult, compared to e.g. iterative fibonacci. The benefit of the recursive solution is more obvious.