Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How not to teach recursion (2021)

parentheticallyspeaking.org

Post reply on HN
Print view View original

51–60 of 121 posts

Re: How not to teach recursion (2021)

#51

Post by dreamcompiler »

dreamcompiler wrote: post #46

My 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…

Exercise: Based on the above discussion, why should squaring an n-digit number be faster than multiplying 2 different n-digit numbers?

Re: How not to teach recursion (2021)

#52

Post by a-dub »

DeathArrow wrote: post #23

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 because math. fact and fib demonstrate this nicely.

would prefer if programming languages offered a recursive decorator that would cause compilation or linting failures if tco isn't possible though.

Re: How not to teach recursion (2021)

#53

Post by lgas »

red_trumpet wrote: post #33

> An attempt at a better answer might be that a problem is “inherently” recursive. However, that’s just a limitation of viewpoint. There’s nothing more inherently recursive than iterative about factorial. All the problems above can be expressed even more declaratively, as in a mathematical specification, that eliminates any implementation directive (e.g.: the greatest common divisor is the greatest, common, divisor:…

I think the point is that you can implement Euclid's algorithm (or any algorithm) iteratively as well as recursively. So there's nothing inherently iterative or recursive about any particular solution, let alone about any particular problem.

Re: How not to teach recursion (2021)

#54

Post by analog31 »

DeathArrow wrote: post #23

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 of proof. When I finally got a chance to learn programming (in 1981), recursion was taught as something we already knew, being related to induction.

Re: How not to teach recursion (2021)

#56

Post by edflsafoiewq »

dreamcompiler wrote: post #46

My 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.

Re: How not to teach recursion (2021)

#57

Post by superjan »

DeathArrow wrote: post #23

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 would agree with the author that there are other, more useful examples of recursion. He gave a family tree example but for me ‘list all files on your hard disk’ would be a better example.

Tail call recursion is interesting, but that belongs in an FP course, which is usually taught long after the basics of programming.

Re: How not to teach recursion (2021)

#58

Post by edflsafoiewq »

viewfromafar wrote: post #39
markisus wrote: post #30

Earlier quoted context omitted.

What does smaller caller mean in this case?

This probably is supposed to hint at a termination order. If a call to a recursive function terminates, then it it often (not always) possible to identify an ordering relation among the arguments of the call and the argument of the recursive call(s) within. Though, there is also the Ackermann function... so for some recursive functions it is not be as easily seen why they would terminate.

> (not always)

Doesn't this work: consider the call graph of all possible argument lists (with an edge A->B if f(A) calls f(B)). If the function terminates, there are no cycles, so this is a DAG, which puts a partial order on the set of argument lists which strictly decreases with each call.

Re: How not to teach recursion (2021)

#59

Post by jimhefferon »

lifthrasiir wrote: post #27
wk_end wrote: post #15

The tl;dr here is “just use HtDP” (which I agree with).

Shriram Krishnamurthi, the author of this piece, happens to be also one of the authors of HtDP.

Was there a link on the web page pointing to the author? I must have overlooked it somehow.

Re: How not to teach recursion (2021)

#60

Post by TheOtherHobbes »

analog31 wrote: post #54
DeathArrow wrote: post #23

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…

Which is closer to how it should be taught.

The factorial example is trivial and too familiar. It's easy for students to think "Oh, I know that" when in fact they don't get it at all.

Recursive operations on data structures are more likely to be unfamiliar. And you need something unfamiliar to demonstrate the point and also illustrate how it's likely to be used in practice.

Post reply on HN