Earlier quoted context omitted.
A simpler way multiplication is recursive is the way it is defined for natural numbers in mathematics: a × b = 0 if b = 0 a × b = a + a × (b - 1) if b ≠ 0
a x b = a if b = 1
What is a + a x 0? :)
How not to teach recursion (2021)
91–100 of 121 posts
Re: How not to teach recursion (2021)
#92I 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…
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))
)Re: How not to teach recursion (2021)
#93I 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…
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).
Calculatiny addition using Peano axioms, that is recursion.
Re: How not to teach recursion (2021)
#94My favorite recursion example is multiplication. Multiplying two numbers is inherently recursive, even though we don't typically think of it that way. (Following is expressed in base 10 for clarity, but in base 2, the multiplications by powers of 10 are of course merely shifts so they don't cost anything.) 68628933 * 26973931 = (6862 * 3931) * 10000 + (2697 * 8933) * 10000 + (6862 * 2697) * 10000 * 10000 + (8933 * 39…
Even the basic schoolbook algorithms are recursive a * (10*b + c) = 10*(a*b) + (a*c) In fact the usual method is even non-tail recursive, you build up a (literal!) stack of intermediate results which you sum back up at the end.
The usual method is iterative:
for digit in a, for digit in b, multiply digits and offset by sum of indices of digits. The sun results.
Re: How not to teach recursion (2021)
#95I 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…
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…
That would require OS specific APIs which are distracting.
Re: How not to teach recursion (2021)
#96I agree with the overall sentiment. I taught for awhile and was happy with the approach I came up with. Students start out with the basics of learning how to loop through a list to transform some data. Once they have looping down, they are introduced to map and other built in methods. But, before using these methods, they are tasked with rewriting them using the looping they've learned. Once they've "earned" the usag…
> but this time without using any kind of looping.
See, to me, recursion is a kind of looping.
Re: How not to teach recursion (2021)
#97The fact that the recursive method for calculating factorials fails for quite small numbers is a good reason for teaching it. Also it's a good illustration of how useless recursion is in practice.
Iterative methods for calculating factorials also "fail for quite small numbers" in most common languages (basically, anything without built-in bignums). The cause of failure in this case has nothing to do with recursion.
also you want to teach: why is iterative factorial faster than recursive? and , why do some (arbitrarily) large recursive factorials crash while the iterative equivalent just takes a long time ? (stack overflow)
IMHO we don't teach compsci kids enough about the costs of things - new vs. * for example
Re: How not to teach recursion (2021)
#98I 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…
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…
[deleted]
Re: How not to teach recursion (2021)
#99Earlier 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…
That would require OS specific APIs which are distracting.
No post body was provided.
Re: How not to teach recursion (2021)
#100> But I’m here to tell you they got it wrong, and everyone’s been getting it wrong ever since. Students come away underwhelmed and baffled, and go on to become the next generation of teachers who repeat this process.
Yeah, this is how recursion works. "If it ain't broke, don't fix it" maybe?