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

71–80 of 121 posts

Re: How not to teach recursion (2021)

#71

Post by Someone »

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…

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

Re: How not to teach recursion (2021)

#72

Post by viewfromafar »

edflsafoiewq wrote: post #58
viewfromafar wrote: post #39

Earlier quoted context omitted.

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.

(I need sleep, Ackermann is actually very easy to show as decreasing using lexicographic order).

Yeah, if you know that the recursive function always terminates, then you know that each recursive call makes the set of remaining steps strictly smaller.

When you want to prove termination, then it is exactly what you need to show (that the remaining work does get smaller, no cycles).

Re: How not to teach recursion (2021)

#73

Post by jlokier »

edflsafoiewq wrote: post #58
viewfromafar wrote: post #39

Earlier quoted context omitted.

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.

You may find the Collatz conjecture interesting: https://en.wikipedia.org/wiki/Collatz_conjecture

It's an easy to understand loop, which can be written as a recursive function of one argument.

Even though the possible arguments are just the natural numbers, nobody knows how to identify a suitable ordering relation which decreases with each call.

Re: How not to teach recursion (2021)

#74

Post by tralarpa »

klysm wrote: post #66

I agree you should start with the data structure. Give someone a recursive data structure and have them try to write a function that does stuff with it.

Yes, a binary tree and a simple function, like calculating the sum of all node values. That's a no-brainer. The funny thing is that when you present it the students first find it obvious (e.g. "sum = value of node + sum of left child + sum of right child, yes, easy, makes sense"), but then they start to think about it and then comes the "wait, why does that work???" phase, and it turns out they had not understand how procedure calls, arguments, and local variables really work up to that point.

Re: How not to teach recursion (2021)

#75

Post by uhhyeahdude »

songzme wrote: post #62

I've been a SWE for 12 years and has been teaching people how to code during my free time ever since I started coding (so more than 12 years of teaching). I have taught around 30 students over the past 12 years who went from knowing nothing to getting a SWE job and from my limited dataset I have observed that: 1. Students who were taught for/while loops first has a hard time grasping recursion. I suspect it is becaus…

Your site looks and reads fantastic; I can’t wait to give it a shot!

Re: How not to teach recursion (2021)

#76

Post by jlokier »

alecbz wrote: post #16
bsedlm wrote: post #2

I'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…

> A recursive definition is: "natural numbers are 0 or a natural number + 1".

Note that this isn't enough by itself to support proof by induction.

Consider the definition of a list in Haskell which is analogous to the above definition of natural numbers: "lists are [] or a list with an element prepended".

Infinite lists satisfy this definition.

Re: How not to teach recursion (2021)

#77

Post by jonsen »

jimhefferon wrote: post #59
lifthrasiir wrote: post #27

Earlier quoted context omitted.

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.

The home page has it:

https://parentheticallyspeaking.org/

Re: How not to teach recursion (2021)

#78

Post by sideshowb »

anon946 wrote: post #44
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…

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.

I've done a few integrals of x from zero to one, they come up quite a bit if x is normalized.

Exception proves the rule, though ;-)

Re: How not to teach recursion (2021)

#79

Post by contravariant »

edflsafoiewq wrote: post #56
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.

I think most schoolbook algorithms are tail recursive.

They're a bit hard to write down otherwise.

Post reply on HN