8 ms·
How not to teach recursion (2021)
- bsedlm 4y agoI'm still looking to understand the difference between recursive definitions and inductive ones...
- onion2k 4y agoIf you've looked at recursive functions then you should also look at recursive functions.
- pwdisswordfish9 4y agoIteration is just recursion over a list/array/generator.
- alecbz 4y agoI don't know if that's a helpful framing? def sum(arr): total = 0 for x in arr: total += x return total and def sum(arr): if len(arr) == 0: return 0 return arr[0] + sum(arr[1:]) both operate over an array but I'd call one of them recursive and the other iterative.
- samth 4y agoI think the closest short answer is that recursive definitions are just a special case of inductive ones for writing functions.
- alecbz 4y agoDo 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"
- cheese_it 4y agoBut 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.
- jlokier 4y ago> 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.
- cloogshicer 4y agoWhile 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.
- bitwize 4y agoA 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.
- omnicognate 4y agoInfinite 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".
- SilasX 4y agoI 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.)
- Borrible 4y agoJust let it speak for itself.
- deleted 4y ago[deleted]
- vga805 4y agoI 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.
- deathanatos 4y ago> but this time without using any kind of looping. See, to me, recursion is a kind of looping.
- vga805 4y agoYeah 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.
- wk_end 4y agoThe tl;dr here is “just use HtDP” (which I agree with).
- SkyMarshal 4y agoI 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.
- lifthrasiir 4y agoShriram Krishnamurthi, the author of this piece, happens to be also one of the authors of HtDP.
- jimhefferon 4y agoWas there a link on the web page pointing to the author? I must have overlooked it somehow.
- jonsen 4y agoThe home page has it: https://parentheticallyspeaking.org/ https://parentheticallyspeaking.org/
- jimhefferon 4y agoThanks. 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.
- deleted 4y ago[deleted]
- im3w1l 4y agoWhere 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.
- layer8 4y agoHowever, 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.
- layer8 4y agoThey 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.
- lifthrasiir 4y agoThe 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).
- layer8 4y agoAh, 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.
- pixelbreaker 4y agoI feel like I've read this before
- taneq 4y agoThe first mistake in teaching recursion is to make the first mistake in teaching recursion.
- DeathArrow 4y agoI 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 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.
- deleted 4y ago[deleted]
- anon946 4y agoAgree. 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.
- sideshowb 4y agoI'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 ;-)
- a-dub 4y agoi 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.
- w0mbat 4y agoI would teach it like this: https://news.ycombinator.com/item?id=31782387 https://news.ycombinator.com/item?id=31782387
- dugmartin 4y agoThe 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.”
- markisus 4y agoWhat does smaller caller mean in this case?
- viewfromafar 4y agoThis 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.
- edflsafoiewq 4y ago> (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.
- viewfromafar 4y ago(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).
- jlokier 4y agoYou may find the Collatz conjecture interesting: https://en.wikipedia.org/wiki/Collatz_conjecture 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.
- tromp 4y ago> Towers of Hanoi 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);
- red_trumpet 4y ago> 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?
- lgas 4y agoI 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.
- Myrmornis 4y agoI 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".
- JulianChastain 4y agoI 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
- __t__ 4y agoI 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
- ledauphin 4y agoagreed - 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.
- dang 4y agoRelated: How Not to Teach Recursion - https://news.ycombinator.com/item?id=25610690 https://news.ycombinator.com/item?id=25610690 - Jan 2021 (9 comments)
- dreamcompiler 4y agoMy 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 * 3931) And then we notice that (6862 * 3931) can be expressed as (68 * 31) * 100 + (39 * 62) * 100 + (68 * 39) * 100 * 100 + (62 * 31) and so on for the 3 remaining products. And then each of these two-digit multiplications can in principle be subdivided into 4 1-digit multiplications. 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_application https://en.wikipedia.org/wiki/Karatsuba_algorithm#Recursive_... [1] https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strasse...
- dreamcompiler 4y agoExercise: Based on the above discussion, why should squaring an n-digit number be faster than multiplying 2 different n-digit numbers?
- edflsafoiewq 4y agoEven 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.
- contravariant 4y ago
- bigbacaloa 4y agoThe 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.
- dale_glass 4y ago> 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
- bigbacaloa 4y agoThe 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.
- Turing_Machine 4y agoIterative 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.
- Taniwha 4y agoalso 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
- bigbacaloa 4y agoI 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.
- tiagod 4y agoI 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.
- songzme 4y agoI'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 https://c0d3.com
- uhhyeahdude 4y agoYour site looks and reads fantastic; I can’t wait to give it a shot!
- addcninblue 4y agoMy 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).
- songzme 4y ago> 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.
- psyklic 4y agoIMO 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.
- klysm 4y agoI 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.
- tralarpa 4y agoYes, 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.
- CraigJPerry 4y agoThe 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.
- ummwhat 4y agoMaybe 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.
- nonsapreiche 4y agoPerfect! I'll add not to teach recursion (or any hi lev math) before 14teen
- quickthrower2 4y agoYou must your kids: 1. Recursion 2. Teach your kids this entire comment
- deleted 4y ago[deleted]
- js2 4y agoHow 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-larry-page-and-sergey-brin-part-2 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.
- robocat 4y ago> 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.
- skribanto 4y agoHow is a family TREE not a tree
- knappa 4y agoEventually 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.
- robocat 4y agoThe 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) https://en.wikipedia.org/wiki/Tree_(data_structure) [2] https://en.wikipedia.org/wiki/Directed_acyclic_graph https://en.wikipedia.org/wiki/Directed_acyclic_graph [3] https://www.scientificamerican.com/article/humans-are-all-more-closely-related-than-we-commonly-think/ https://www.scientificamerican.com/article/humans-are-all-mo... [4] https://en.wikipedia.org/wiki/Mitochondrial_Eve https://en.wikipedia.org/wiki/Mitochondrial_Eve [5] https://en.wikipedia.org/wiki/Y-chromosomal_Adam https://en.wikipedia.org/wiki/Y-chromosomal_Adam
- nonsapreiche 4y agoteach recursion not "How not to teach recursion (2021) (parentheticallyspeaking.org)" (trees,permutations,graphs..)
- marcodiego 4y agoTo teach recursion you have to teach what is a base case and what is recursion.
- emergant 4y agoWhat 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 4y ago[deleted]
- idnfus 4y ago
- deleted 4y ago[deleted]
- omazurov 4y ago> 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?
- Lerc 4y agoMy 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.
- CodeWriter23 4y agoIteration > Recursion
- apricot 4y agoI 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.
- musicale 4y agoSee: How Not to Teach Recursio