How not to teach recursion (2021)(parentheticallyspeaking.org)
parentheticallyspeaking.org
How not to teach recursion (2021)
https://parentheticallyspeaking.org/articles/how-not-to-teach-recursion/
120 comments
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.
>>> 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.
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.
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.
Induction isn't recursion. Induction is why recursion works.
Unless you are assuming ZFC, which is much more comlplex then recursion itself, in second-order logic Induction is an axiom that we use to avoid recursion, by setting up the recursive step and then saying "so we don't have to execute it and look further"
Constructing the naturals is dynamic programming (building up), not recursion (breaking down).
Calculatiny addition using Peano axioms, that is recursion.
Unless you are assuming ZFC, which is much more comlplex then recursion itself, in second-order logic Induction is an axiom that we use to avoid recursion, by setting up the recursive step and then saying "so we don't have to execute it and look further"
Constructing the naturals is dynamic programming (building up), not recursion (breaking down).
Calculatiny addition using Peano axioms, that is recursion.
We hadn't gotten to those kinds of concepts in school by the time I learned recursion. The math that confounds programmers is much more basic.
Most of the time a sequence of numbers is recursively defined. Ex. Xn = Xn-1 + 2n
So a student might be familiar with it.
So a student might be familiar with it.
It was counterproductive for me when recursion was taught with Fibonacci and factorials. They were literally the opposite of easy to understand for me, I had absolutely no idea why those examples actually worked, so I just gave up and treated them like magic.
I think recursion should be taught with examples that would be easier for a student to write with recursion than without it. For example, listing all files in a directory.
I think recursion should be taught with examples that would be easier for a student to write with recursion than without it. For example, listing all files in a directory.
Why would you think enumerating a directory is not magic?
Walking a tree / BFS is quite easy to implement iteratively, using a search queue. It's a common example for teaching Lisp.
Recursion is most natural in problems like implementing evaluation of an abstract syntax trer:
Walking a tree / BFS is quite easy to implement iteratively, using a search queue. It's a common example for teaching Lisp.
Recursion is most natural in problems like implementing evaluation of an abstract syntax trer:
eval(tree) =
apply(node(tree),
map(eval, leaves(tree))
)And since a tree is a graph, you can just use adjacency matrix and two loops. :)
O(n^2) but very simple.
O(n^2) but very simple.
[deleted]
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.
Tail call recursion is interesting, but that belongs in an FP course, which is usually taught long after the basics of programming.
I completely agree with this. The trouble also is that "real" recursive problems tend to be _very_ hard: an example from physics would be magnetohydrodynamics where a plasma moves in accordance to an applied external B field, causing a current to flow, which generates a B field that changes how the plasma flows...you get the idea.
Everyone knows that you don't _really_ want to try doing 123! using your "my first recursion" code in C. Similarly everyone knows that factorial gets pretty big pretty quickly – I remember finding out the limits of calculators in school by finding at which point x! went from "big number" to "error". It's pedagogically useful for those things and you can see (a) if your answer is right, compared to a BigNum library, and (b) how long it takes. There's a whole can of worms you can go down, from Sterling's approximation to a discussion about time complexity, ints and IEEE 754, and stack overflows. You could then go waffling about, e.g. Haskell and lazy evaluation and functional programming and so on.
Factorial isn't a good problem but it's common enough that students will have heard of it, deep enough to be interesting, and used so frequently as a programming example that if you see a recursive definition of factorial in another programming language you get that they're trying to teach you about recursion. It's a good teaching tool for all those reasons.
Everyone knows that you don't _really_ want to try doing 123! using your "my first recursion" code in C. Similarly everyone knows that factorial gets pretty big pretty quickly – I remember finding out the limits of calculators in school by finding at which point x! went from "big number" to "error". It's pedagogically useful for those things and you can see (a) if your answer is right, compared to a BigNum library, and (b) how long it takes. There's a whole can of worms you can go down, from Sterling's approximation to a discussion about time complexity, ints and IEEE 754, and stack overflows. You could then go waffling about, e.g. Haskell and lazy evaluation and functional programming and so on.
Factorial isn't a good problem but it's common enough that students will have heard of it, deep enough to be interesting, and used so frequently as a programming example that if you see a recursive definition of factorial in another programming language you get that they're trying to teach you about recursion. It's a good teaching tool for all those reasons.
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.
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.
>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.
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 every iteration. at the least this defeats gains from caches, at worst it defeats them entirely by filling them with junk.
but, if the problem is small enough it can be worth it for the correctness guarantees and increased simplicity.
trivial iterative algorithms are simpler, sure, but when things get more complicated, recursion can replace very hard to understand, test and debug iterative code with simple recursive definitions where guarantees of correctness and termination come for free.
non-flattened recursive algorithms spread their state across linear memory with a full stack frame for every iteration. at the least this defeats gains from caches, at worst it defeats them entirely by filling them with junk.
but, if the problem is small enough it can be worth it for the correctness guarantees and increased simplicity.
trivial iterative algorithms are simpler, sure, but when things get more complicated, recursion can replace very hard to understand, test and debug iterative code with simple recursive definitions where guarantees of correctness and termination come for free.
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.
so it turns out that optimization is also tco (tail call optimization). that said, i was previously unfamiliar with continuous passing style, thanks!
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 ;-)
Exception proves the rule, though ;-)
[deleted]
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 usage of the built in methods, they are tasked with rewriting them again, but this time without using any kind of looping. I give them a bit of time to think about how they may do this. Very few students get it but the plan is to live code it myself as an introduction to recursion. The task is still the same: to rewrite the map method. So the context for their intro to recursion is something they've become quite familiar with. It seems to have worked well.
Once they've "earned" the usage of the built in methods, they are tasked with rewriting them again, but this time without using any kind of looping. I give them a bit of time to think about how they may do this. Very few students get it but the plan is to live code it myself as an introduction to recursion. The task is still the same: to rewrite the map method. So the context for their intro to recursion is something they've become quite familiar with. It seems to have worked well.
> but this time without using any kind of looping.
See, to me, recursion is a 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.
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 because following the recursive callstack gets tricky and feels unintuitive. This inspired me to try a curriculum where I teach students recursion first and don't expose them for/while loops until they are prepping for interviews.
2. Students who were taught recursion first has no problem understanding for/while loops when they were exposed to it.
For people who are curious, I used to teach students at my local library but recently created a free online curriculum at: https://c0d3.com
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 because following the recursive callstack gets tricky and feels unintuitive. This inspired me to try a curriculum where I teach students recursion first and don't expose them for/while loops until they are prepping for interviews.
2. Students who were taught recursion first has no problem understanding for/while loops when they were exposed to it.
For people who are curious, I used to teach students at my local library but recently created a free online curriculum at: https://c0d3.com
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).
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).
> 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.
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.
Your site looks and reads fantastic; I can’t wait to give it a shot!
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.)
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...
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...
Even the basic schoolbook algorithms are recursive
a * (10*b + c)
= 10*(a*b) + (a*c)
The usual method is iterative:
for digit in a, for digit in b, multiply digits and offset by sum of indices of digits. The sun results.
for digit in a, for digit in b, multiply digits and offset by sum of indices of digits. The sun results.
I think most schoolbook algorithms are tail recursive.
They're a bit hard to write down otherwise.
They're a bit hard to write down otherwise.
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 ≠ 0Exercise: Based on the above discussion, why should squaring an n-digit number be faster than multiplying 2 different n-digit numbers?
> 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 tree (hi uncle grandma), and that it’s leaf boundaries are fuzzy. Or is that the point?
Apart from the fact that in a modern children’s classroom, bringing up parental discussions is going to be very complicated by other factors.
> These confuse recursion with cyclicity. If you don’t understand the difference, don’t use the dumb jokes.
Well, except cyclicity has a bunch of different meanings - I did a quick search and didn’t find a good reference for the sense they are using.
Isn’t this a horrific example for recursion? Wouldn’t most adults realise that the structure isn’t a tree (hi uncle grandma), and that it’s leaf boundaries are fuzzy. Or is that the point?
Apart from the fact that in a modern children’s classroom, bringing up parental discussions is going to be very complicated by other factors.
> These confuse recursion with cyclicity. If you don’t understand the difference, don’t use the dumb jokes.
Well, except cyclicity has a bunch of different meanings - I did a quick search and didn’t find a good reference for the sense they are using.
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 </unfunny-black-humour>.
[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
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 </unfunny-black-humour>.
[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
Eventually your (for example) great*N paternal grandfather is going to show up on your mother's side, forming a loop. That's just due to bounds on the human population and how the number of labels for previous generations grows exponentially backwards in time.
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
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.
The author mentions the HTDP approach - and it’s a really great book, for more reasons than just the careful treatment of recursion - but there’s an even more obvious book choice for this topic (and it shares an author of HTDP); the little schemer.
The Little Schemer is a fraction of the size of HTDP and it’s focussed on this exact problem.
The Little Schemer is a fraction of the size of HTDP and it’s focussed on this exact problem.
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".
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".
How not to teach recursion, Sergey Brin and Larry Page edition. (From an 2003 interview on NPR's Fresh Air.)
http://www.npr.org/2003/10/14/167643282/google-founders-larr...
Starting at 13:45 it goes like this:
Terry Gross: Now I'll tell you, in preparing for this, I decided, let me Google Google, so I typed in "Google" into the Google search, and I came up with a lot of Google things in the regular search, but in the "Are you feeling lucky?" search, I got nothing.
Larry Page: Well you just got Google itself.
TG: Yeah, I just got Google itself. Oh, I see, Google was giving me itself.
LP: Yeah.
TG: Oh.
LP: In computer science, we call that recursion. [laugh].
TG: Oh, you even have a name for it. [laugh]. I didn't quite get that. I kept thinking it was just repeating itself. I didn't realize it was giving me itself. [laugh].
LP: [laugh]
TG: And what's the name for it?
LP: Uh, recursion. It's... kind of... Sergey is giving me a dirty look.
TG: Why?
LP: It's a loose definition. [laugh]
TG: Lighten up Sergey. [laugh]
LP: It's a loose interpretation of... [laugh]... recursion.
TG: Sergey, what's the more literal interpretation?
Sergey Brin: The technical term is you got itself back.
TG: Right?
SB: There's not really much beyond that. [laugh]
TG: Okay.
SB: Idempotence. How about that?
TG: Say it again.
SB: Idempotence.
TG: What is it?
SB: That's when you uh... [laugh]... Maybe I should stop while I'm ahead...
TG: ...You're just making this up, aren't you...
SB: ...Before I dig a deeper hole. Idempotence is when you do something and you get the original thing back.
TG: Oh, so that's a real word?
LP: It's a mathematical term.
SB: Yeah, yeah, but it's also just as loose an interpretation as Larry's was of recursion.
http://www.npr.org/2003/10/14/167643282/google-founders-larr...
Starting at 13:45 it goes like this:
Terry Gross: Now I'll tell you, in preparing for this, I decided, let me Google Google, so I typed in "Google" into the Google search, and I came up with a lot of Google things in the regular search, but in the "Are you feeling lucky?" search, I got nothing.
Larry Page: Well you just got Google itself.
TG: Yeah, I just got Google itself. Oh, I see, Google was giving me itself.
LP: Yeah.
TG: Oh.
LP: In computer science, we call that recursion. [laugh].
TG: Oh, you even have a name for it. [laugh]. I didn't quite get that. I kept thinking it was just repeating itself. I didn't realize it was giving me itself. [laugh].
LP: [laugh]
TG: And what's the name for it?
LP: Uh, recursion. It's... kind of... Sergey is giving me a dirty look.
TG: Why?
LP: It's a loose definition. [laugh]
TG: Lighten up Sergey. [laugh]
LP: It's a loose interpretation of... [laugh]... recursion.
TG: Sergey, what's the more literal interpretation?
Sergey Brin: The technical term is you got itself back.
TG: Right?
SB: There's not really much beyond that. [laugh]
TG: Okay.
SB: Idempotence. How about that?
TG: Say it again.
SB: Idempotence.
TG: What is it?
SB: That's when you uh... [laugh]... Maybe I should stop while I'm ahead...
TG: ...You're just making this up, aren't you...
SB: ...Before I dig a deeper hole. Idempotence is when you do something and you get the original thing back.
TG: Oh, so that's a real word?
LP: It's a mathematical term.
SB: Yeah, yeah, but it's also just as loose an interpretation as Larry's was of recursion.
Where recursion really shines is when an iterative method would need an explicit stack, and a recursive one can use the call stack. Depth first search comes to mind.
However, since stack space is usually much smaller than heap space, if the problem size depends on external input and doesn’t have a sufficiently low limit, one either has to perform an appropriate size check beforehand or use an explicit stack after all.
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.
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.
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.
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.
(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).
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).
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.
Maybe the trick is to just teach it young. I first learned about the towers of Hanoi when I was about 14. Blew my mind. It was like circular reasoning that worked somehow.
Unlike a lot of people, I don't have this fear/anxiety about recursion. In fact the opposite. I friggin love recursion. I actively seeking out the recursive answer. It doesn't hurt my brain. In fact the opposite, it's gratifying on an almost sexual level. At some point in my apartment we had a recursion bin next to the recycling and normal trash. Inside of it was a power strip plugged into itself.
Maybe the trick with recursion is to teach it while the brain is still a bit plastic. Don't assume teens are too dumb. Talk to your kids about recursion, before it's too late.
Unlike a lot of people, I don't have this fear/anxiety about recursion. In fact the opposite. I friggin love recursion. I actively seeking out the recursive answer. It doesn't hurt my brain. In fact the opposite, it's gratifying on an almost sexual level. At some point in my apartment we had a recursion bin next to the recycling and normal trash. Inside of it was a power strip plugged into itself.
Maybe the trick with recursion is to teach it while the brain is still a bit plastic. Don't assume teens are too dumb. Talk to your kids about recursion, before it's too late.
You must your kids:
1. Recursion 2. Teach your kids this entire comment
1. Recursion 2. Teach your kids this entire comment
Perfect! I'll add not to teach recursion (or any hi lev math) before 14teen
[deleted]
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.
[deleted]
IMO A major mistake books make is immediately attempting to visualize the call stack. This is important to be able to do. However, practitioners will simply imagine the code working on an arbitrary element and somewhat ignore the call stack (except perhaps for debugging).
I disagree that factorial is not "applied" enough -- no matter what problem you choose, it will be interesting to some students and not others. The entire purpose of recursion is not speed, but to more aptly fit your mental model -- resulting in simpler code.
In that light, I am also surprised that the article did not explain that recursion is essentially solving a problem in terms of a simpler problem, e.g. n! = n*(n-1)!, which eventually becomes the trivial case 0! = 1.
I disagree that factorial is not "applied" enough -- no matter what problem you choose, it will be interesting to some students and not others. The entire purpose of recursion is not speed, but to more aptly fit your mental model -- resulting in simpler code.
In that light, I am also surprised that the article did not explain that recursion is essentially solving a problem in terms of a simpler problem, e.g. n! = n*(n-1)!, which eventually becomes the trivial case 0! = 1.
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.
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.
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.
[deleted]
[deleted]
I think the family tree example would work better upside down, as you can easily state a problem that is obviously more intuitive to solve recursively (depth first search).
Start by defining a node object (a person) which contains a name and a list of their offspring (other nodes).
Find if the given starting node or any of their descendants have a certain first name, or some other property.
Start by defining a node object (a person) which contains a name and a list of their offspring (other nodes).
Find if the given starting node or any of their descendants have a certain first name, or some other property.
My go to has always been Line Drawing.
If the line is <= one pixel long, draw a pixel, otherwise draw a line from each end to the midpoint.
Not the best or efficient line drawing method, but you can immediately use it for stuff once it's made, and using something that you understand how it works counts for a lot when you're learning.
Not the best or efficient line drawing method, but you can immediately use it for stuff once it's made, and using something that you understand how it works counts for a lot when you're learning.
> But I’m here to tell you they got it wrong, and everyone’s been getting it wrong ever since. Students come away underwhelmed and baffled, and go on to become the next generation of teachers who repeat this process.
Yeah, this is how recursion works. "If it ain't broke, don't fix it" maybe?
Yeah, this is how recursion works. "If it ain't broke, don't fix it" maybe?
While I agree with the overall argument, reading this was a bit frustrating. The article made all kinds of interesting points and observations, but didn't really explain any of them. For example, I'd love to know what the difference between recursion and cyclicity is.
I don't even think it made interesting points, just "haha, who uses factorials and Fibonacci numbers?" and "I bet students don't like programming the same thing in different ways." (No? That part definitely interests me, but either way it depends on what would resonate with your student audience.)
A recursive definition for something makes reference to that self-same definition, but it always has a base case to break the endless regress. Non-programming example: in grammar, a noun phrase might be defined as a noun, or a modifier and a noun phrase.
Infinite recursion (without a base case) is still recursion and, with tail call optimisation, can be useful in practice for the same reasons infinite loops can be useful.
I don't really see why the author doesn't see the joke as recursive. If it's about the lack of a base case they're misguided. Maybe the author is distinguishing between functions that recurse by calling themselves directly (direct recursion) and ones that call themselves via other functions (indirect recursion). Or maybe it's about recursive functions vs cyclic data structures. Or maybe it's something else as neither of those explains why the quoted joke is incorrect either.
You'd think in a section titled "Recursion vs Cyclicity" the author would make some effort to explain the difference, but apparently that matters less to them than calling things "dumb".
I don't really see why the author doesn't see the joke as recursive. If it's about the lack of a base case they're misguided. Maybe the author is distinguishing between functions that recurse by calling themselves directly (direct recursion) and ones that call themselves via other functions (indirect recursion). Or maybe it's about recursive functions vs cyclic data structures. Or maybe it's something else as neither of those explains why the quoted joke is incorrect either.
You'd think in a section titled "Recursion vs Cyclicity" the author would make some effort to explain the difference, but apparently that matters less to them than calling things "dumb".
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 n(n+1)/2: 0*(0+1)/2 = 0, and (n+1) + n(n+1)/2 = (2(n+1) + n(n+1))/2 = (2n + 2 + n^2 + n)/2 = (n^2 + 3n + 2)/2 = (n+1)(n+2)/2 = (n+1)((n+1)+1)/2"
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 n(n+1)/2: 0*(0+1)/2 = 0, and (n+1) + n(n+1)/2 = (2(n+1) + n(n+1))/2 = (2n + 2 + n^2 + n)/2 = (n^2 + 3n + 2)/2 = (n+1)(n+2)/2 = (n+1)((n+1)+1)/2"
> 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.
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.
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.
I think the closest short answer is that recursive definitions are just a special case of inductive ones for writing functions.
Iteration is just recursion over a list/array/generator.
I don't know if that's a helpful framing?
def sum(arr):
total = 0
for x in arr:
total += x
return total
def sum(arr):
if len(arr) == 0:
return 0
return arr[0] + sum(arr[1:])
> Towers of Hanoi
This also suffers from having a non-recursive solution, using bit-manipulation of a binary counter:
This also suffers from having a non-recursive solution, using bit-manipulation of a binary counter:
max = 1 << no_of_discs;
for (x = 1; x < max; x++)
printf("move a disc from %d to %d\n", (x&x-1)%3, ((x|x-1)+1)%3);> 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?
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?
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.
Related:
How Not to Teach Recursion - https://news.ycombinator.com/item?id=25610690 - Jan 2021 (9 comments)
How Not to Teach Recursion - https://news.ycombinator.com/item?id=25610690 - Jan 2021 (9 comments)
To teach recursion you have to teach what is a base case and what is recursion.
The 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.
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
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
teach recursion not "How not to teach recursion (2021) (parentheticallyspeaking.org)"
(trees,permutations,graphs..)
(trees,permutations,graphs..)
I feel like I've read this before
The first mistake in teaching recursion is to make the first mistake in teaching recursion.
See: How Not to Teach Recursio
The tl;dr here is “just use HtDP” (which I agree with).
I would also include The Little Schemer and Learn You a Haskell For Great Good in the “further reading/references” section. They also explain recursion well.
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/
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.
Iteration > Recursion
I would teach it like this: https://news.ycombinator.com/item?id=31782387
Too many redirects, missing base case.
Just let it speak for itself.
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.
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.
The cause of failure in this case has nothing to do with recursion.
also you want to teach: why is iterative factorial faster than recursive? and , why do some (arbitrarily) large recursive factorials crash while the iterative equivalent just takes a long time ? (stack overflow)
IMHO we don't teach compsci kids enough about the costs of things - new vs. * for example
IMHO we don't teach compsci kids enough about the costs of things - new vs. * for example
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.
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.
What a pretentious take, mathematical concepts that have a recursive variation are not appropriate as a learning tool because "we don't use them"? Since when do we stop teaching recursion after the canonical examples? Do we not teach tree traversals right after? The mathematical examples demonstrate exactly what they are designed to do, the effects of a function called by it self. Tree traversals (or any other abstract data structure traversal) demonstrates side effects might happen in between. Learning anything is a iterative process and that is exactly what the canonical examples are for: an entry point for the learning process.
[deleted]
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 teaching I think it is very important to so teach tail call recursion and to teach when to use recursion. Because it can be a waste to use recursion if an easy to implement iterative solution exists.