I feel like I've read this before
How not to teach recursion (2021)
21–30 of 121 posts
Re: How not to teach recursion (2021)
#22Where recursion really shines is when an iterative method would need an explicit stack, and a recursive one can use the call stack. Depth first search comes to mind.
However, since stack space is usually much smaller than heap space, if the problem size depends on external input and doesn’t have a sufficiently low limit, one either has to perform an appropriate size check beforehand or use an explicit stack after all.
Re: How not to teach recursion (2021)
#23I see nothing wrong with either factorial or Fibonacci numbers.
The author argues that nobody uses or needs neither factorial nor Fibonacci numbers.
But that is not the point. If you are going to teach a concept it's best to use easy to understand examples. And factorial Fibonacci numbers are just that. I rather use factorial to teach recursion than QuickSort using Hoare partition algorithm.
And if it comes about teaching I think it is very important to so teach tail call recursion and to teach when to use recursion. Because it can be a waste to use recursion if an easy to implement iterative solution exists.
Re: How not to teach recursion (2021)
#24I would teach it like this: https://news.ycombinator.com/item?id=31782387
Re: How not to teach recursion (2021)
#25I would teach it like this: https://news.ycombinator.com/item?id=31782387
Too many redirects, missing base case.
Re: How not to teach recursion (2021)
#26While I agree with the overall argument, reading this was a bit frustrating. The article made all kinds of interesting points and observations, but didn't really explain any of them. For example, I'd love to know what the difference between recursion and cyclicity is.
A recursive definition for something makes reference to that self-same definition, but it always has a base case to break the endless regress. Non-programming example: in grammar, a noun phrase might be defined as a noun, or a modifier and a noun phrase.
Infinite recursion (without a base case) is still recursion and, with tail call optimisation, can be useful in practice for the same reasons infinite loops can be useful.
I don't really see why the author doesn't see the joke as recursive. If it's about the lack of a base case they're misguided. Maybe the author is distinguishing between functions that recurse by calling themselves directly (direct recursion) and ones that call themselves via other functions (indirect recursion). Or maybe it's about recursive functions vs cyclic data structures. Or maybe it's something else as neither of those explains why the quoted joke is incorrect either.
You'd think in a section titled "Recursion vs Cyclicity" the author would make some effort to explain the difference, but apparently that matters less to them than calling things "dumb".
Re: How not to teach recursion (2021)
#27The tl;dr here is “just use HtDP” (which I agree with).
Shriram Krishnamurthi, the author of this piece, happens to be also one of the authors of HtDP.
Re: How not to teach recursion (2021)
#28The best summary I’ve heard and remembered was from my undergraduate data structures professor over 30 years ago. It has a nice rhyming structure: “every recursive function has a base case and a smaller caller.”
Re: How not to teach recursion (2021)
#29> Towers of Hanoi
This also suffers from having a non-recursive solution, using bit-manipulation of a binary counter:
max = 1 Re: How not to teach recursion (2021)
#30The best summary I’ve heard and remembered was from my undergraduate data structures professor over 30 years ago. It has a nice rhyming structure: “every recursive function has a base case and a smaller caller.”
What does smaller caller mean in this case?