I disagree with the reasoning for why factorial is a bad example. Factorial is very simple to explain as a mathematical function, requires very little prior knowledge. When asked why you aren't allowed to implement it as a loop, the response I was given was that you very simply define factorial in a self referential way (0! = 1 and n! = n * (n - 1)!), and is there any way you could implement the function in a way that clearly expresses that definition? At least for me this function was a fantastic intro to recursion
How not to teach recursion (2021)
41–50 of 121 posts
Re: How not to teach recursion (2021)
#42I 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…
[deleted]
Re: How not to teach recursion (2021)
#43I'm still looking to understand the difference between recursive definitions and inductive ones...
Do people talk about "inductive definitions"? I mostly only hear about induction in the context of proofs, in which case I'd say that an inductive proof/argument is one that uses the recursive structure of whatever it's about. A recursive definition is: "natural numbers are 0 or a natural number + 1". An (abridged) inductive proof that uses the recursive nature of natural numbers: "the sum of all naturals up to n is…
But how do you know that induction is valid to use on natural numbers? It's because their definition/construction follows a set of rules that makes them inductive. Some languages like Coq make this explicit by providing an 'Inductive' keyword for defining inductive types.
Re: How not to teach recursion (2021)
#44I 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…
Agree. You could use the argument that argument against almost any teaching example. Like, when's the last time you ever needed to integrate x from 0 to 1? I've never needed to do that. Or when is the last time you needed to know how long a 1 kg ball will take to fall from 1 m? At least in my opinion, the way the author thinks recursion should be taught seems to needlessly complicate it.
Re: How not to teach recursion (2021)
#45I disagree with the reasoning for why factorial is a bad example. Factorial is very simple to explain as a mathematical function, requires very little prior knowledge. When asked why you aren't allowed to implement it as a loop, the response I was given was that you very simply define factorial in a self referential way (0! = 1 and n! = n * (n - 1)!), and is there any way you could implement the function in a way tha…
I agree factorial is very clearly defined with self-references but I think that the answers have no clear meaning and that's why its not an optimal way of teaching recursion. Teaching examples that have meaningful answers IMO allow for much better reasoning
Re: How not to teach recursion (2021)
#46My 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 * 3931)
(68 * 31) * 100
+ (39 * 62) * 100
+ (68 * 39) * 100 * 100
+ (62 * 31)
The reason the algorithm is recursive is that we're really talking about polynomial multiplication, which is convolution. (Other kinds of multiplication (e.g. dot products) are not convolution and this discussion doesn't apply to them.)
The above is interesting and curious, but is it useful? Yes. Karatsuba multiplication [0] exploits this recursion and adds some clever algebra to reduce the total number of multiplication instructions needed and thus speed up bignum multiplication.
For even bigger numbers, the Schönhage–Strassen algorithm [1] goes even further and uses the Fourier transform to convert the overarching convolution operation to element-by-element (dot-product style) multiplication.
[0] https://en.wikipedia.org/wiki/Karatsuba_algorithm#Recursive_...
[1] https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strasse...
Re: How not to teach recursion (2021)
#47The fact that the recursive method for calculating factorials fails for quite small numbers is a good reason for teaching it.
Also computing the factorial is one of the first examples illustrating that recursion is useless in practice.
Re: How not to teach recursion (2021)
#48The 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.
Re: How not to teach recursion (2021)
#49Related:
How Not to Teach Recursion - https://news.ycombinator.com/item?id=25610690 - Jan 2021 (9 comments)
Re: How not to teach recursion (2021)
#50The fact that the recursive method for calculating factorials fails for quite small numbers is a good reason for teaching it. Also computing the factorial is one of the first examples illustrating that recursion is useless in practice.
> The fact that the recursive method for calculating factorials fails for quite small numbers is a good reason for teaching it.
That variables can overflow is a valuable thing to teach, but it shouldn't be something the student bumps into during the lesson on recursion