3 ms·
They don’t mention “divide and conquer” at all, which I find a pretty compelling use of recursion even for non-inherently recursive problems. Writing a merge so
by layer8 4y ago
They don’t mention “divide and conquer” at all, which I find a pretty compelling use of recursion even for non-inherently recursive problems. Writing a merge sort recursively is much easier and clearer than the nonrecursive variant.
- lifthrasiir 4y agoThe 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.