4 ms·
You don't really understand how difficult recursion is until you've tried to teach a bunch of programming newcomers the concept. A few get it quickly, but for t
by ballenf 9y ago
You don't really understand how difficult recursion is until you've tried to teach a bunch of programming newcomers the concept. A few get it quickly, but for the rest all the "think of it like ..." suggestions don't really help. It's a concept that everyone seems to have to learn through practice (as the author implies). I fell into the trap that if I only explained it clearly enough I could make it easy for others. Everyone learns it their own way and you just have to give students enough opportunities to practice for them to get it. I don't disagree with Dijkstra that the concept shouldn't be difficult, but I do not believe there are any easy paths to the concept for most.
It's one of the most interesting learning processes in that once you get it, it feels almost as simple as a for loop or simple math. But until you get it it feels like the most opaque, impenetrable wall where 1+1 != 2.
Side note, recursion would be slightly easier if the concept of a base case were applied to all functions as preconditions. The idea of a base case really has more applicability than just in recursion, it's just that we don't call it a base case in other situations.
Recursion is also interesting to implement when doing TDD. It comes in a refactoring step, of course, but you don't have to think about the base case(s) because they've already been done. Again, not suggesting this is helpful to a newcomer struggling, but is just an interesting process.
- macintux 9y agoSide note, recursion would be slightly easier if the concept of a base case were applied to all functions as preconditions. The idea of a base case really has more applicability than just in recursion, it's just that we don't call it a base case in other situations. Function heads in ML and Erlang make this explicit when used correctly, and I agree.
- ballenf 9y agoAnd I need to learn those languages really before thinking I really know recursion!
- patrickthebold 9y agoCan you expand on "base case for all functions"? I'm having a hard time figuring out a base case for say calling toString on an object, or incrementing an integer.
- ballenf 9y agoNo because that comment was poorly worded and overbroad. I'll narrow it to say that drawing a parallel between base cases and preconditions might be helpful when dealing with functions / methods that are more complex than lambdas or their equivalents. Thanks, I should have thought through that part more carefully before posting.
- falcor84 9y ago> I'm having a hard time figuring out a base case for say calling toString on an object, or incrementing an integer. In both cases, we can special-case the "zero" of the domain. For example, toString of an object without any attributes would return '{}', while incrementing the integer zero would return 1. I'm not sure about the usability of the latter in an iterative approach, but the former could definitely be used as the basis of an iterative algorithm that traverses all of an object's attributes.
- chowells 9y agoCorecursion doesn't require base cases, and it's a perfectly useful way to write programs in languages that support lazy evaluation. I'm not sure base cases are as important as you suggest.