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

111–120 of 121 posts

Re: How not to teach recursion (2021)

#111

Post by ledauphin »

__t__ wrote: post #45
JulianChastain wrote: post #41

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

agreed - it's the intuitiveness of the answer to the example that is so critical to building understanding. When you want to teach a method, it's much better if the student already knows what the result should be by a different method, so they can see how the new method is different than the one they know.

Re: How not to teach recursion (2021)

#112

Post by vga805 »

deathanatos wrote: post #96
vga805 wrote: post #14

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

Yeah fair enough, I agree, I could have worded that differently. They couldn't use any of the looping they'd come to learn up to that point.

Re: How not to teach recursion (2021)

#113

Post by addcninblue »

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…

My background is in teaching CS1 courses in undergrad (as a TA).

There have been various studies that agree with you: teaching recursion before iteration seems to have benefits! From my experience, it seems to be extremely unpopular among teachers due to the claim that recursion is "useless in industry". My personal opinion is that learning recursion first is probably a step in the right direction, but I'm curious to hear your thoughts (in terms of their claims of the usefulness of recursion in industry).

Re: How not to teach recursion (2021)

#114

Post by jimhefferon »

jonsen wrote: post #77
jimhefferon wrote: post #59

Earlier quoted context omitted.

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/

Thanks. I'm a big fan of SK's but he has made a mistake (yes, it is a small one). Pages should have a link to the home.

Re: How not to teach recursion (2021)

#115

Post by robocat »

skribanto wrote: post #106
robocat wrote: post #70

> For instance, even a child informed about biology can answer basic questions like these: - Does a child have (biological) parents? - Yes. - How many? - Two, a (biological) male and (biological) female. [...] They can similarly see other kinds of self-referential data even at a young age, well before they program. Isn’t this a horrific example for recursion? Wouldn’t most adults realise that the structure isn’t a tr…

How is a family TREE not a tree

The word tree[1] has a specific meaning when talking about computer science (recursion). An idealised biological family tree is a DAG (directed acyclic graph[2]), because there are cross linkages creating common ancestors, although I am also presuming we define when to stop adding nodes.

An actual family tree is not even a DAG because the nodes are unknown, and “parents” is an extremely fuzzy concept. Where does adoption fit it? What about step-parents? How do you record uncertainty? Etcetera.

One of my friends in another country had a kid with her first cousin, and parents can be more closely related biologically.

It is less than one hundred generations before we find a single common ancestor to everyone alive[3]. Also see [4][5].

Regardless, anyone that thinks using a family tree as a teaching example for children should have a reëducation holiday .

[1] https://en.wikipedia.org/wiki/Tree_(data_structure)

[2] https://en.wikipedia.org/wiki/Directed_acyclic_graph

[3] https://www.scientificamerican.com/article/humans-are-all-mo...

[4] https://en.wikipedia.org/wiki/Mitochondrial_Eve

[5] https://en.wikipedia.org/wiki/Y-chromosomal_Adam

Re: How not to teach recursion (2021)

#116

Post by songzme »

addcninblue wrote: post #113
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…

My background is in teaching CS1 courses in undergrad (as a TA). There have been various studies that agree with you: teaching recursion before iteration seems to have benefits! From my experience, it seems to be extremely unpopular among teachers due to the claim that recursion is "useless in industry". My personal opinion is that learning recursion first is probably a step in the right direction, but I'm curious to…

> recursion is "useless in industry"

From my experience its true. I have never written recursive code in my 12 years of professional experience (primarily JS).

But during interviews, I have written recursive solutions many times to solve some of the harder problems.

Re: How not to teach recursion (2021)

#117

Post by apricot »

I agree with the author that recursive data structures are a good starting point from which to teach recursion. My favorite example is writing a program that computes the disk space used in a directory, including all of its subdirectories. It's very practical and immediately interesting to students, and they are motivated to understand why it works.

It also helps if students have been exposed to the idea of recursion in math, for example by sequences where a_n is defined in terms of a_{n-1}, and/or proofs by induction.

Re: How not to teach recursion (2021)

#119

Post by Akronymus »

a-dub wrote: post #109
DeathArrow wrote: post #103

Earlier quoted context omitted.

>i think the problem is that most people try to follow the recursions in their head which is hard. It's hard for computers, too as it can easy result in stack overflow if there are too many steps.

that's the obvious issue. another less intuitive one is that modern cpus and compilers are essentially optimized for iterative algorithms. state variables can be kept in registers, simd can be used for data that appears in contiguous arrays, caching is built on locality assumptions and data locality is preserved. non-flattened recursive algorithms spread their state across linear memory with a full stack frame for ev…

If you go with a continuous passing style (which more often than not is relatively "easy") the compiler usually optimize it to replacing/reusing the frame rather than allocating a new one.

Re: How not to teach recursion (2021)

#120

Post by bigbacaloa »

Turing_Machine wrote: post #63
bigbacaloa wrote: post #48

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

I didn't express myself well. That naive computations of factorials are useless for computing 50! is a useful lesson.

It's also useful to learn that despite the love of recursion among computer scientists, in practice it's barely if ever a good idea.

Post reply on HN