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

31–40 of 121 posts

Re: How not to teach recursion (2021)

#31

Post by lifthrasiir »

layer8 wrote: post #20

They don’t mention “divide and conquer” at all, which I find a pretty compelling use of recursion even for non-inherently recursive problems. Writing a merge sort recursively is much easier and clearer than the nonrecursive variant.

The divide-and-conquer algorithm is a subset of what the post calls generative recursion, which requires a non-trivial amount of logic to get it right (even the simplest algorithm like binary search can be surprisingly difficult).

Re: How not to teach recursion (2021)

#33

Post by red_trumpet »

> 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: the definition of the problem says nothing about how to find it, and searching through all numbers to find divisors that are common and taking the largest one is no less valid a solution).

I always thought Euclid's algorithm had a pretty great runtime complexity, compared to "list all divisors, choose the greates common one". Is that not correct?

Re: How not to teach recursion (2021)

#34

Post by layer8 »

lifthrasiir wrote: post #31
layer8 wrote: post #20

They don’t mention “divide and conquer” at all, which I find a pretty compelling use of recursion even for non-inherently recursive problems. Writing a merge sort recursively is much easier and clearer than the nonrecursive variant.

The divide-and-conquer algorithm is a subset of what the post calls generative recursion, which requires a non-trivial amount of logic to get it right (even the simplest algorithm like binary search can be surprisingly difficult).

Ah, the post neglected to explain what they mean by generative recursion. The difficulties however are “just” in off-by-one errors and in the boundary cases of fixed-size integer types, which don’t get in the way if understanding the solution approach. You can easily understand it without having to understand recursive data structures. In that aspect, it shares the simplicity with fibonacci etc., but is more compelling than those because the alternative iterative solution is more difficult, compared to e.g. iterative fibonacci. The benefit of the recursive solution is more obvious.

Re: How not to teach recursion (2021)

#37

Post by tromp »

carnitine wrote: post #32
tromp wrote: post #29

> Towers of Hanoi This also suffers from having a non-recursive solution, using bit-manipulation of a binary counter: max = 1

Every recursive problem has a non-recursive solution.

True; but this one manages to avoid using an explicit stack.

Re: How not to teach recursion (2021)

#38

Post by Myrmornis »

I have some comments on how (not) to teach it.

First of all, do not tell students to "start with the base case". The base case will be trivial and gives very little insight into how to solve the recursion problem. All the time they spend thinking about that is time spent not confronting the actual problem.

Beyond that, I think the way to teach recursion is to say "You cannot write the code until you can write a sentence in words describing the recursive solution. Your sentence must make reference to calling the procedure on a smaller sub-problem. Don't bother describing the base case in the sentence; it's boring - just fill it out when you write the code.".

So something like "The number of ways the robot can get to the last square is equal to the number of ways it can do it assuming it starts by going right plus the number of ways it can do it assuming it starts by going down".

Re: How not to teach recursion (2021)

#39

Post by viewfromafar »

markisus wrote: post #30
dugmartin wrote: post #28

The best summary I’ve heard and remembered was from my undergraduate data structures professor over 30 years ago. It has a nice rhyming structure: “every recursive function has a base case and a smaller caller.”

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.

Re: How not to teach recursion (2021)

#40

Post by dugmartin »

markisus wrote: post #30
dugmartin wrote: post #28

The best summary I’ve heard and remembered was from my undergraduate data structures professor over 30 years ago. It has a nice rhyming structure: “every recursive function has a base case and a smaller caller.”

What does smaller caller mean in this case?

I’ve always took it to mean the search space of the function needs to narrow to approach the base case so that it can terminate. In factorial this means subtracting 1, in tree searches it means picking one of the children, in parsing it means selecting a production that narrows the matches, etc.
Post reply on HN