101–110 of 121 posts
Earlier quoted context omitted.
It was counterproductive for me when recursion was taught with Fibonacci and factorials. They were literally the opposite of easy to understand for me, I had absolutely no idea why those examples actually worked, so I just gave up and treated them like magic. I think recursion should be taught with examples that would be easier for a student to write with recursion than without it. For example, listing all files in a…
Why would you think enumerating a directory is not magic? Walking a tree / BFS is quite easy to implement iteratively, using a search queue. It's a common example for teaching Lisp. Recursion is most natural in problems like implementing evaluation of an abstract syntax trer: eval(tree) = apply(node(tree), map(eval, leaves(tree)) )
O(n^2) but very simple.
I 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 tea…
i think the problem is that most people try to follow the recursions in their head which is hard. the biggest lesson regarding recursion is that if you're lucky enough to have your problem fit with tco (or have guarantees your problem is small enough), it's actually way simpler to both write and verify. write the base case, write the inductive step, translate to code, done. no hard reasoning about the code required b…
It's hard for computers, too as it can easy result in stack overflow if there are too many steps.
I 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 tea…
This might be the root of the problem for the author: >>> In principle, natural numbers are also recursive data: a number is either zero or the successor of another natural number. However, this way of thinking is not natural to students... That's because students didn't learn math. "Back in my day," we learned mathematical induction sometime in middle school, and were re-introduced to it from time to time as a style…
So a student might be familiar with it.
> For instance, even a child informed about biology can answer basic questions like these: - Does a child have (biological) parents? - Yes. - How many? - Two, a (biological) male and (biological) female. [...] They can similarly see other kinds of self-referential data even at a young age, well before they program. Isn’t this a horrific example for recursion? Wouldn’t most adults realise that the structure isn’t a tr…
> For instance, even a child informed about biology can answer basic questions like these: - Does a child have (biological) parents? - Yes. - How many? - Two, a (biological) male and (biological) female. [...] They can similarly see other kinds of self-referential data even at a young age, well before they program. Isn’t this a horrific example for recursion? Wouldn’t most adults realise that the structure isn’t a tr…
How is a family TREE not a tree
Earlier quoted context omitted.
i think the problem is that most people try to follow the recursions in their head which is hard. the biggest lesson regarding recursion is that if you're lucky enough to have your problem fit with tco (or have guarantees your problem is small enough), it's actually way simpler to both write and verify. write the base case, write the inductive step, translate to code, done. no hard reasoning about the code required b…
>i think the problem is that most people try to follow the recursions in their head which is hard. It's hard for computers, too as it can easy result in stack overflow if there are too many steps.
non-flattened recursive algorithms spread their state across linear memory with a full stack frame for every iteration. at the least this defeats gains from caches, at worst it defeats them entirely by filling them with junk.
but, if the problem is small enough it can be worth it for the correctness guarantees and increased simplicity.
trivial iterative algorithms are simpler, sure, but when things get more complicated, recursion can replace very hard to understand, test and debug iterative code with simple recursive definitions where guarantees of correctness and termination come for free.
Earlier quoted context omitted.
This might be the root of the problem for the author: >>> In principle, natural numbers are also recursive data: a number is either zero or the successor of another natural number. However, this way of thinking is not natural to students... That's because students didn't learn math. "Back in my day," we learned mathematical induction sometime in middle school, and were re-introduced to it from time to time as a style…
Induction isn't recursion. Induction is why recursion works. Unless you are assuming ZFC, which is much more comlplex then recursion itself, in second-order logic Induction is an axiom that we use to avoid recursion, by setting up the recursive step and then saying "so we don't have to execute it and look further" Constructing the naturals is dynamic programming (building up), not recursion (breaking down). Calculati…