Not the above commenter, but I think there are so many algorithms that are easier, even beautiful, when written recursively as opposed to iteratively (e.g. tree traversal, language parsing).
That doesn't mean its natural for humans to understand.
I'm not a normal human, but I recurse. Nearly every problem I have to solve is effectively a tree strucfture that requires depth-first traversal (with some realistic alterations to make it more like A* and a directed graph). I often work down in some deep part of the tree and then when I finish, have to recall my stack and work my way back up towards my original goal. For example, for "create nanotechnology" I am currently on the "stitch images collected from my self-designed microscope into panoramas" and when that's solved I can pop back up to running "collect behavioral data from tardigrades" which will eventually allow myself to pop back up to "modify tardigrades to be cellular assemblers" and then I can work on cellular assemblers that assemble nanites. This has been a 30+ year structure and I occasionally get to pop the stack a bit.
"The stack" can be the state of the thing you're working on. For instance when modelling something with clay, you start with crude shapes, pushing and poking the clay until the crude shape looks more like what you intend, then you reapply this same process at finer and finer levels of detail. The state of the clay from previous operations is your "stack". When you've reached the finest level of detail you care to make you unwind the stack by stepping back to view your work.
Anyway, it's basically just another way of structuring the state of a loop. And if you're doing tail call recursion then the distinction essentially doesn't exist.
Pointers being challenging is the biggest meme in CS education. They're conceptually very simple and the only real challenging part is C's arcane syntax. If you start with assembly for a simple ISA or just teach the concept of pointers first instead of teaching them at the same time as teaching C, then they're dead simple.
Until you try to write an optimizing compiler, run into provenance, and find that they're actually complicated (though not for the reasons beginners think they're complicated).
Pointers aren't hard, the languages used by most intro to CS classes are the hard part. I taught myself z80 assembly in middle school and didn't learn until years later that pointers are supposedly hard. From the direction I learned it, you address memory with numbers, and obviously you can do arithmetic on numbers. This is one of the simplest things in CS to learn. It's the * and & soup that becomes a nightmare to beginners.
Lest you think I'm just a bragard, I never managed to get better than a C in any calculus course.
Pointers are so easy to work with that they're still the cause of major security flaws and crashing programs every single day.
The concept of pointers isn't too hard if you know how memory works, but that hasn't made working with pointers any easier. Any serious work with pointers quickly devolves into questions about ownership, lifetimes, and figuring out the proper sizes. Plus, many educators seem to skip verifying that students actually know how memory works before introducing pointers, which leads some students to believe that pointers are some kind of language feature rather than a core concept of modern computer hardware.
I always tell people that I understand pointers because I once made one out of gates. This may be a case where teaching a simple microprocessor architecture would reap a lot of benefits. My first was the Z80, simply because there was a book about it at Radio Shack.
IMO, the biggest mistake in C syntax was using the same character for both the dereferencing operator and the pointer type declarator. I'm convinced it's responsible for the majority of the confusion about pointers.
I have so far seen only two reasons that “hard” CS concepts are hard:
1) It’s reputedly hard, but isn’t at all, so I spend way more time convincing myself I’m not missing something (“I must be…”) than I do learning it. Pointers; recursion; “dynamic programming”; various concepts that basically only Haskellers talk about.
2) A huge proportion of explanations are just, unaccountably, confusing as hell and make it seem way more complicated than it is. Bad beginner OO explanations; literally any explanation of anything in which the examples are in Haskell.
Testing if somebody groks recursion or pointers is the easiest litmus test to see if somebody "groks" programming. They're not "easy" concepts, and usually people have had to break through a wall for it to be comfortable with them. They make great interview questions, doesn't need to be long or complex problem, just has to have either pointers or recursion in it.
Perhaps it is just me but I have a degree in CS, programmed in c for 10 years then C# for 10 years an I can't follow anything about that article claiming recursion is simple.
Yes that's my take too. Once you know something well, it's easy to formulate it elegantly to say it's nothing more than the monoid in the category of endofunctors or whatever, but how something is conceptualized by those who get it has no bearing on how it's learned. A lot of the time, it seems like lots of worked examples without any theory is the way to go until something clicks.
All that said, I can't understand why someone would find recursion complicated which probably means I'm unsuitable to teach it.
This is Polish notation [1], which puts a symbol for the function at the front of a term and the arguments of that function after it. So (* 2 3) is what you'd usually write as 2*3.
So you can read this code:
(define (expt n p)
(if (equals? p 1)
n
(* n (expt n (- p 1)))
As this more typical psuedocode
function expt(n,p):
if p = 1:
return n
return n * exp(n, p-1)
It is challenging and annoying, and people like these who say it isn't in a gloating manner were a major reason I considered changing my major from CS in undergrad.
I'm very different from you. In physics, there were always somebody telling you that something was trivial and somehow the proof was elegant. It irritated me, but I always went and figured it out for myself out of spite. Spite will get you a long way through adversity!
I ended up getting a CS degree, but the obnoxious gatekeeping mentality that everything is easy needs to end - it turns off A LOT of people from studying STEM.
I've learned to ignore articles calling anything "simple" or "non-challenging" if they involve Scheme in their explanation.
I know Scheme is a basic programming language and a nice demonstration of how syntax trees work, but I've only seen the programming language used by academics who have been doing research for so long that they have no idea about what is and isn't simple for students anymore.
Recursion is quite easy when you get it. The problem is that "getting it" is very difficult. Even if you think you get it because you've figured out how to use it, you may not really get it. The worst part is that the same explanation can resonate with some and not with others, but most educators and textbooks I've seen pick one "correct" way to explain a concept and stick with it, so if you're not part of the segment of students for which that type of explanation works, you're out of luck and will need to figure that stuff out on your own.
It is easy once you get it. So easy, in fact, that you are tempted to forget that it was ever hard.
Using recursion safely requires a less natural pattern of thought than if/while/for. Once you get it, sure, it's easy. But lets not trivialize the initial struggle either.
If there's any single takeaway from recent advances in deep learning, it's that multilayer neural nets allow the simulation of recursion, which is absolutely fundamental to any kind of meaningful reasoning.
Struggling through mathematical notation, or learning technical material in school, can be brutal. Never confuse the medium with the message.
Coming from a math background and going into algorithms class, recursion was much easier to grasp than for loops. It really is a pedagogy thing.
I think it comes from the fact that lot of CS majors go into college with years of experience with for loops and barely knowing what recursion is. If you start from a blank slate, I am confident recursion is much easier to understand.
For loops don't require keeping track of multiple levels of state; you just need a counter. It's very easy to walk through a for-loop on pen and paper. Walking through recursion is much trickier since you have to keep track of your stack.
But you don't need to "walk through" recursion, you just need to assume the sub-calls do the correct thing. That's the magic of it -- like induction in proofs, if you convince yourself that the function does the correct thing if all of its self-calls do the correct thing, then your function is totally correct.
Induction is basically the first thing you learn in your freshman intro to proofs class. Probably US high school geometry classes teach it too, I don't remember, but it can be easily taught to sophomore high school students. So you saying it's not intuitive is a bias that came from your previous experience, not from reality.
Induction is literally the simplest type of proof you do in math, and of course there's a 1-1 relationship between induction and recursion. Induction is also the basic way that you discover/invent an algorithm in CS, which is usually taught in junior level CS algorithms classes in all the top colleges.
So I think it's just a problem with people just not learning a fairly simple concept or just skipping intro to algo classes altogether.
Since it's simple, the question of whether it is intuitive or not depends on how well you learn it. It's such a core part of algorithm design that you should make it intuitive to yourself in order to be a better programmer.
Induction should be intuitive. I think there are a few things that get lost. One is you need to show the steps are equivalent. You have to show going from n-1 to n is similar to going from n to n+1.
My favorite analogy is coming stairs. You prove you can get from the floor to the first step (that is the base case) but you also have to show that all the stairs are identical. I think this is where a lot of people misunderstand induction.
Math background here too. Long before I first sat down at a computer (in 1981), we learned about the inductive principle in math class, and did some proofs with it. Later on, our introduction to recursion (in Pascal) started with a review of induction.
Of course the next phase is trying to do everything with recursion.
I am confident, from remembering the troubles other students had when recursion was introduced, that recursion is indeed very difficult for some students.
I'm not even sure that iteration was easy for them.
Just because it is easy for one person does not make it easy for another. There are some people who love high school geometry and hate high School trigonometry, and vice versa, because the former deals with proofs for the most part and the latter deals with application (at least when I was taught it).
Probably because it's taught badly. From one of the other responses:
> you just need to assume the sub-calls do the correct thing.
This is technically correct (and I remember hearing it when first learning recursion), but it's not useful. The two most common problems were not having a good stopping condition, and handling two or more levels per call because they didn't understand at what point the function should call itself.
I think the first thing that needs to happen is just draw a diagram of common data structures and show how they can be looked at as a recursive data structure. Like a tree is a node and two more trees, or a list is a node and another list. As odd as it may sound to some people, I think starting with something that has a visual representation like that (even if it's more complicated in code) is easier to understand than pure math like recursive fibonacci.
This would also double as an answer to the "why would I use this when I can just use a loop?" question. Just challenge the student to walk a tree with loops instead of recursion to see how much more work it is.
One difficulty in learning about recursion is the "you're allowed to do that?" aspect, where defining something in terms of itself can feel "incomplete" or "circular".
This problem is possibly confounded by the fact that some recursive definitions in computer science are "incomplete" or "circular" (they can be proved not to terminate, or cannot be proved to terminate, and so can't actually be evaluated!).
We're used to the idea that a circular argument (the original sense of "beginning the question") is unpersuasive and that a circular definition or answer is unhelpful. So it's subtle to see when a partly self-referential definition can actually be usable.
In functional programming languages you might only be able to use recursion when you can prove it always reaches the base case (to define a total function), but that requirement is itself somewhat subtle!
I think recursion is easiest to understand as syntactic sugar for stack manipulation. It always terminates because stacks have finite size. I don't see the point of having an "elegant" mathematical definition of something when it's unrelated to real hardware.
I don't understand the title here in relation to the rest of the article. The author seems to be arguing that recursion should be easily understood, and the fact that students find it challenging must be the teachers' fault because the author has no problem with it.
But they never get around to explaining how to teach it better, so why do they say we should cease labeling it as challenging?
Recursion is a trick. It’s a beautiful, elegant, concise trick, but it’s not at all intuitive to most humans.
The problem with for loops isn’t the loop. Loops are easy to understand. The problem with for loops is that you have to maintain mutable state across iterations, which quickly gets very complicated. Recursion is useful specifically because it doesn’t need mutable state.
I think recursion is incredibly intuitive if you just start with an obviously recursive data structure. Give someone a tree, and writing a recursive function is a very natural thing to do.
Lists are an even simpler recursive structure, but people really struggle with the idea of head vs. tail. Using a for loop to iterate a list is way easier for beginners to understand. Even experts usually prefer a list comprehension over explicit recursion.
Sure, which is why high-level languages manage the stack pointer for you. You can get a long way with pure functional recursion before you have to worry about annoying details, like tail calls and stack sizes.
And the RAM your computer is writing everything to is mutable! And someone could come along and bash your computer with a hammer -- it would feel awfully mutable then! Everything is mutable if you consider the upcoming heat death of the universe.
The point is that within the abstraction you're working in, recursion is entirely immutable, and loops are not. Good programmers selectively forget about stack pointers and RAM and the heat death of the universe when they're writing code -- they put on the correct "costume" for the part of code they're in and they never go "out of character". Worrying about the stack pointer is like having your Starbucks cup in the shot of Game of Thrones. Danaerys Targaryen doesn't know WTF Starbucks is and your programming avatar should not know WTF a stack pointer is.
OP is plagiarizing blog posts at scale, across lots of different throwaway HN accounts and fake Substack blogs.
They appear to be going through old Hacker News submissions, finding the source content, and then publishing those posts on blogs that they created. Here's when the real post was submitted to HN, back in 2011: https://news.ycombinator.com/item?id=2440364
OP, would you care to share more about your scam? What do you get from it?
Here's other examples where they did the same thing using different Substacks and different HN accounts - this is just a subset:
Maybe we need to start doing like my university's math and engineering departments did to combat plagiarism: keep a very long history of automatic Bayesian and structural similarity analysis of every electronic homework and lab submission from a multitude of participating campuses.
Sounds like a viable startup business idea IYAM but would need institutional and/or platform champions for initial beta users.
IIRC, the system didn't exchange plaintext to nodes on other campuses. It passed signatures and each institution maintained their own collections for definitive comparison because the most common case was submitting someone else's work from another year. It was the era of barely high speed internet.
Perhaps with the advent of generative LLMs, this will assist in the generation of entirely personalized university assignments and exams making "replay attack" cheating impossible. Hopefully, LLMs will also semi-automate correctness verification of exams and correct answers.
69 comments
[ 3.2 ms ] story [ 133 ms ] thread(If you have a tail-call optimization, many kinds of recursive process don't require a stack and don't risk an OOM condition!)
That doesn't mean its natural for humans to understand.
I understand that there are lots of algorithmic tasks that are best understood that way, and that those aren't what you were talking about.
If you can sit through 5m of slides: https://github.com/lelanthran/frame/blob/master/docs/FrameIn...
Anyway, it's basically just another way of structuring the state of a loop. And if you're doing tail call recursion then the distinction essentially doesn't exist.
Is this a humblebrag post?
Lest you think I'm just a bragard, I never managed to get better than a C in any calculus course.
The concept of pointers isn't too hard if you know how memory works, but that hasn't made working with pointers any easier. Any serious work with pointers quickly devolves into questions about ownership, lifetimes, and figuring out the proper sizes. Plus, many educators seem to skip verifying that students actually know how memory works before introducing pointers, which leads some students to believe that pointers are some kind of language feature rather than a core concept of modern computer hardware.
1) It’s reputedly hard, but isn’t at all, so I spend way more time convincing myself I’m not missing something (“I must be…”) than I do learning it. Pointers; recursion; “dynamic programming”; various concepts that basically only Haskellers talk about.
2) A huge proportion of explanations are just, unaccountably, confusing as hell and make it seem way more complicated than it is. Bad beginner OO explanations; literally any explanation of anything in which the examples are in Haskell.
(* n (* n (expt n (p-1))) etc...
huhhh?
and yes, I can do recursion.
People get so used to patterns of thought, they forget what they had to do to get there.
Anyway, that unindented code hurts my eyes. (It's not as bad as an unmatched parenthesis, but it's close.)
All that said, I can't understand why someone would find recursion complicated which probably means I'm unsuitable to teach it.
So you can read this code:
As this more typical psuedocode Or the more mathematical framing: [1] https://en.wikipedia.org/wiki/Polish_notationI know Scheme is a basic programming language and a nice demonstration of how syntax trees work, but I've only seen the programming language used by academics who have been doing research for so long that they have no idea about what is and isn't simple for students anymore.
Recursion is quite easy when you get it. The problem is that "getting it" is very difficult. Even if you think you get it because you've figured out how to use it, you may not really get it. The worst part is that the same explanation can resonate with some and not with others, but most educators and textbooks I've seen pick one "correct" way to explain a concept and stick with it, so if you're not part of the segment of students for which that type of explanation works, you're out of luck and will need to figure that stuff out on your own.
It is easy once you get it. So easy, in fact, that you are tempted to forget that it was ever hard.
Using recursion safely requires a less natural pattern of thought than if/while/for. Once you get it, sure, it's easy. But lets not trivialize the initial struggle either.
Struggling through mathematical notation, or learning technical material in school, can be brutal. Never confuse the medium with the message.
https://www.bishopbook.com
I think it comes from the fact that lot of CS majors go into college with years of experience with for loops and barely knowing what recursion is. If you start from a blank slate, I am confident recursion is much easier to understand.
Induction is literally the simplest type of proof you do in math, and of course there's a 1-1 relationship between induction and recursion. Induction is also the basic way that you discover/invent an algorithm in CS, which is usually taught in junior level CS algorithms classes in all the top colleges.
So I think it's just a problem with people just not learning a fairly simple concept or just skipping intro to algo classes altogether.
(Maybe a bad example; I feel like it shows that people are familiar with coinduction.)
Of course the next phase is trying to do everything with recursion.
I'm not even sure that iteration was easy for them.
Just because it is easy for one person does not make it easy for another. There are some people who love high school geometry and hate high School trigonometry, and vice versa, because the former deals with proofs for the most part and the latter deals with application (at least when I was taught it).
> you just need to assume the sub-calls do the correct thing.
This is technically correct (and I remember hearing it when first learning recursion), but it's not useful. The two most common problems were not having a good stopping condition, and handling two or more levels per call because they didn't understand at what point the function should call itself.
I think the first thing that needs to happen is just draw a diagram of common data structures and show how they can be looked at as a recursive data structure. Like a tree is a node and two more trees, or a list is a node and another list. As odd as it may sound to some people, I think starting with something that has a visual representation like that (even if it's more complicated in code) is easier to understand than pure math like recursive fibonacci.
This would also double as an answer to the "why would I use this when I can just use a loop?" question. Just challenge the student to walk a tree with loops instead of recursion to see how much more work it is.
This problem is possibly confounded by the fact that some recursive definitions in computer science are "incomplete" or "circular" (they can be proved not to terminate, or cannot be proved to terminate, and so can't actually be evaluated!).
We're used to the idea that a circular argument (the original sense of "beginning the question") is unpersuasive and that a circular definition or answer is unhelpful. So it's subtle to see when a partly self-referential definition can actually be usable.
In functional programming languages you might only be able to use recursion when you can prove it always reaches the base case (to define a total function), but that requirement is itself somewhat subtle!
But they never get around to explaining how to teach it better, so why do they say we should cease labeling it as challenging?
The problem with for loops isn’t the loop. Loops are easy to understand. The problem with for loops is that you have to maintain mutable state across iterations, which quickly gets very complicated. Recursion is useful specifically because it doesn’t need mutable state.
The point is that within the abstraction you're working in, recursion is entirely immutable, and loops are not. Good programmers selectively forget about stack pointers and RAM and the heat death of the universe when they're writing code -- they put on the correct "costume" for the part of code they're in and they never go "out of character". Worrying about the stack pointer is like having your Starbucks cup in the shot of Game of Thrones. Danaerys Targaryen doesn't know WTF Starbucks is and your programming avatar should not know WTF a stack pointer is.
This post was stolen from https://web.archive.org/web/20110416092916/https://jinfiesto...
OP is plagiarizing blog posts at scale, across lots of different throwaway HN accounts and fake Substack blogs.
They appear to be going through old Hacker News submissions, finding the source content, and then publishing those posts on blogs that they created. Here's when the real post was submitted to HN, back in 2011: https://news.ycombinator.com/item?id=2440364
OP, would you care to share more about your scam? What do you get from it?
Here's other examples where they did the same thing using different Substacks and different HN accounts - this is just a subset:
11 years ago: https://news.ycombinator.com/item?id=5337525 (plagiarized and submitted as https://news.ycombinator.com/item?id=40081175)
12 years ago: https://news.ycombinator.com/item?id=3425331 (plagiarized and submitted as https://news.ycombinator.com/item?id=40091392)
13 years ago: https://news.ycombinator.com/item?id=3154446 (plagiarized and submitted as https://news.ycombinator.com/item?id=40150949)
Sounds like a viable startup business idea IYAM but would need institutional and/or platform champions for initial beta users.
Perhaps with the advent of generative LLMs, this will assist in the generation of entirely personalized university assignments and exams making "replay attack" cheating impossible. Hopefully, LLMs will also semi-automate correctness verification of exams and correct answers.