4 ms·
One of my favorite ways of thinking about recursion (and proofs by induction) is the recursion goblins. When you're writing a recursive function, you don't wor
by ketzo 7y ago
One of my favorite ways of thinking about recursion (and proofs by induction) is the recursion goblins.
When you're writing a recursive function, you don't worry about how you got your input. The recursion goblins took care of that.
You also don't need to worry about what will happen to the thing that you return. The recursion goblins will take care of that, too.
All you need to worry about is what's happening in between the curly brackets, which is that you should make your problem a little smaller. The recursion goblins will take care of the rest.
This was weirdly freeing for me in CS 101/102/103 etc.; I was getting way too wrapped up in trying to visualize the recursion from start to finish, and that's a crapshoot at the best of times, even if it's sometimes important. Much more often, though, you can get a lot done a lot faster if you trust the goblins!
(Thanks to Professors Shindler and Cote for this one)
- deleted 7y ago[deleted]
- hinkley 7y agoWorking a problem from bottom-up flushes out a lot of the incidental information, making the problem much easier to comprehend. By using the goblin analogy you're focused on the last call, and working back from there. The Refactoring people knew this, and the Mikado method is essentially a way to find the 'bottom' when all you can see is the top of the rabbit hole, so you can use these other skills.
- redis_mlc 7y agoOne of my favorite ways to think about recursion is that it's a shitty technique that can and will blow up your stack. When I try to solve a problem with recursion, then I have two problems. It's also a great way to filter out morons in interviews. If they ask for a recursive solution, and I tell them that it's a shitty solution, and if they don't immediately agree, then I know I'll be working with morons.
- sundbry 7y agoWow. such smart. Eliet hacker. https://lmgtfy.com/?q=tail+call+optimization https://lmgtfy.com/?q=tail+call+optimization
- tigershark 7y agoNever heard of tail-call optimization, right?
- acchow 7y agoWhy are recursive solutions shitty? I find them easier to read...
- slikts 7y agoRecursion is a powerful, relatively low-level approach, and the price for expressive power is readability, but it has legit use cases. What you said has a grain of truth in that usually you should prefer combinators like map or filter (if you're doing FP), but just throwing away recursion is silly. Having a strong opinion on it and not seeming to know about TCO is also not a good look.
- zelphirkalt 7y agoI don't think it's necessarily more difficult to read, especially with the mindset of the "recursion goblins" mentioned in another comment here, where one only looks at the current iteration and does not care about, where input argument comes from. But of course, if what one wants to do can be expressed using map and filter and such, why write some recursive procedure.
- rlpb 7y agoThe challenge is to decide on the specification of what your function inputs and what it outputs. Get specification right, implement it as you describe (ignoring the task of your recursion goblins), and it'll work. Get the specification wrong, and the implementation will either be difficult or impossible. It is helpful, of course, if someone else has defined a workable specification for you already.