3 ms·
Interesting! I had the exact same experience where recursion really clicked -- proof by induction === recursion. Obviously (in hindsight)! :) And, by extension
by lomnakkus 12y ago
Interesting! I had the exact same experience where recursion really clicked -- proof by induction === recursion. Obviously (in hindsight)! :)
And, by extension, structural induction === sum & product types + pattern matching destructuring for recursive functions. The fact that the type checker can make sure you've got your base cases covered is just gravy.
- platz 12y agoAlthough I think loops and recursion aren't so different: here's a snippet from meijer: "The goal of recursion and loops is exactly the same, you want to define something in terms of itself. That's what the loop does; it repeats a computation and something gets smaller... the loop variable or when you for each over a loop you're picking out the next element.. That's exactly what a recursive definition tries to do, you're trying to define a function, in terms of a smaller version of it's argument." http://channel9.msdn.com/Series/C9-Lectures-Erik-Meijer-Functional-Programming-Fundamentals/C9-Lectures-Dr-Erik-Meijer-Functional-Programming-Fundamentals-Chapter-6-of-13 http://channel9.msdn.com/Series/C9-Lectures-Erik-Meijer-Func...
- tel 12y agoLoops are generally special cases of recursion. You can always derive an iterator from a recursor by forgetting things, but you need product types or ambient state to go the opposite way. In Turing complete languages they're both special cases of fixed-point equations, though, so in that sense they both have the same goal.