4 ms·
This was how I was "taught" recursion, with (Lucas) Towers of Hanoi. Ugh! I still remember the mostly-filled in function with 2(?) recursive calls placed, for
by arh68 7y ago
This was how I was "taught" recursion, with (Lucas) Towers of Hanoi. Ugh! I still remember the mostly-filled in function with 2(?) recursive calls placed, for us to fill in the arguments. How the heck would that ever work? was all I could think. I don't think a single person in the class had any idea of progress until the teacher, kinda exasperated, just told us. And we still didn't get it, of course. I get it now, but only from a more task-oriented mindset, not Java Mad Libs.
The only recursion that still bothers me is Clownsort / Stooge sort [0]. That such an algorithm would work is still not my gut feeling.
[0] https://en.wikipedia.org/wiki/Stooge_sort https://en.wikipedia.org/wiki/Stooge_sort
- nsomani 7y agoI think the intuition behind your Stooge sort example is that for an array separated into three segments: A | B | C The first sort moves the largest elements of A and B into B. The second sort moves the largest elements of B and C (and therefore of A, B, and C) into C. And the final sort properly orders the elements within A and B.
- arh68 7y agoOk but what does your intuition say about the first step? > If the value at the start is larger than the value at the end, swap them. What if we skip that? Broken sort? Is that step necessary, and if so, what's the edge case? Why even mention it? I hope I don't seem combative, I just find my intuition doesn't quite cover this problem.
- deleted 7y ago[deleted]