RFC: Tackling learners' struggles in Core Programming

Problem

This will be a LONG one, please read all of it! (Except parts marked "optional".)

Many learners report difficulties with certain abstract mathematical concepts in "Introduction to Programming and Computer Science", "How to Code" (HtC) and "Programming Languages Part A, B" (PLAB) courses. Specifically, they struggle with: self-similarity, (parametric) types and reasoning about types, recursion, recursive thinking, recursive data types, graphs, trees, cases, pattern matching, and generally using logic and reasoning about code. Some learners report finishing these courses but still not fully understanding them, not feeling like they made progress, frustration with, and desire to skip, these courses. (This RFC is not about replacing these courses. Please do not recommend alternatives.)

Duration

October 28 2022 - January 28 2023 (3 months)

Background

I've helped quite a few learners with the final projects of HtC Simple Data (Space Invaders) and Complex Data (TA scheduling); and also with programming assignments of Prog Lang Parts A, B. Students express this feeling of "not making progress" or "not understanding what they did right" especially after successfully completing a hard recursion exercise, or even a course. Often they repeat mistakes or exhibit misunderstandings they've had 1-2 courses ago.

Similar difficulties with recursion are frequently reported in the MIT Intro to Prog and CS with Python course, especially with the Towers of Hanoi section; so it is not limited to Racket and SML (which some learners dislike).

Something about recursion, recursive data types, and overall "reasoning about code" is just not "clicking" in learners' minds. One frequent impression is: "I've finished these courses but I don't know if they worked out for me. I haven't improved." Some learners naturally get angry and defensive about it.

As a result, the 4-course Recursion Gauntlet of HtC 1,2 + PLAB becomes insurmountable and/or unbearable for some. I get many questions asking if they really need these classes or if they can just skip them (the answer is a resounding NO!). A few learners I've helped regularly over several months dropped off somewhere along these courses. We don't have exact statistics but I think this is where we are bleeding many learners out of the curriculum.

There are also struggles with Graphs and Trees in How to Code: Complex Data. It's the first time in their lives that learners are seeing graphs, and at first it can be very strange.

There are also struggles with the Algorithmic Complexity analysis in "Introduction to Programming and Computer Science with Python" as it assumes Calculus, Big-O notation, growth rates of the most common real-valued functions, and recursive/inductive reasoning (with, for example, Merge Sort).

To a lesser extent, learners have difficulty with Boolean Algebra, Logic Gates and especially the Disjunctive Normal Form algorithm that is required at the beginning of Nand2Tetris Part I. (This is also covered in Unit 1 of Math for CS.)

The "recursion problem"

It turns out that difficulty in learning recursion is a decades long, universal problem (see Appendix for more details). However if many learners are finishing the courses and still struggling with recursion, we should do something about it. An IEEE study says that: "students' perception is that neither motivation, nor their previous knowledge of theoretical concepts on recursion, are factors that affect their learning of the recursion process".

BUT... digging deeper I noticed that recursion itself is not the core of the issue, but just one of the many symptoms.

The usual suspects

Learners usually blame the following things: the instructor/course is bad, the language (say, Racket or SML) is "old" and "outdated", "too many parentheses", "weird syntax", "poor tools/IDE support/no debugger", "recursion is stupid/illogical", and so on. These are clearly not true in the case of Python (Racket has a really good IDE with stepper/debugger, and SML is still actively developed in 2022), and I'd argue not true in general.

It causes many learners to look down on these courses and languages: "I'll never use this in real life", "this is useless" and so on, which misses the overall educational purposes of the courses: the languages being just tools to learn the concepts, and having historical importance paving the way for the newer languages with their innovative ideas. Although I'd agree that the courses don't do the best job of showing real-world consequences of the concepts (for example: immutability and pattern-matching is used a lot in unexpected places like Rust; mutually recursive data is what the entire world is currently using with JSON).

Who is the real suspect?

On the surface it looks like recursion is the true mastermind criminal here, but it's not. It's a general lack of exposure to the underlying abstract mathematical concepts: logic, proofs, reasoning, induction, recursive definitions and how to reason about them using (normal or Structural) Induction.

I believe it's not the learners' fault; it is most likely due to poor educational systems that teach little to no math, logic and rigor in high school. I have written tons of induction proofs in a poor public high school, but I understand that this is not taught in schools anymore (I even learned the cubic formula in high school!). In fact learners from various countries (in my experience, containing but not limited to: Egypt, Brazil, Japan, Israel, Russia, United States) say they learned almost no math at all in high school! There are many poor educational systems all around the world. Learners usually jump into programming courses without taking care of prerequisite math skills first.

Proposal

Make Unit 1: Proofs of Mathematics for Computer Science into a prerequisite for How to Code: Simple Data. (Only Unit 1, nothing more.)

Alternative:

Move all of Core Math before Core Programming, including the 3 Calculus courses.

Rationale for Proposal

List of topics that directly match between the sources of struggle in Core Programming and Unit 1 of Math for CS:

There is an extremely tight and close matching between topics of Unit 1 and the problematic concepts in the Core Programming courses.

Cases and pattern matching <-> Proof by cases

Example from Standard ML in Programming Languages Part A:

fun all_answers(f: 'a -> 'b list option)(alist: 'a list): 'b list option =
    case alist of
        [] => SOME []
    |   a :: alist) =>
        case all_answers f alist of
          NONE => NONE
        | SOME bs =>
            case f(a) of
              NONE => NONE
            | SOME bs' => SOME(bs' @ bs)

From Unit 1 of Math for CS:

proof-by-cases

Recursive Data Types

Examples from Standard ML and Racket:

datatype pattern =
      Wildcard
    | Variable of string
    | UnitP
    | ConstP of int
    | TupleP of pattern list
    | ConstructorP of string * pattern

(define-struct woman (name sons daugters))
(define-struct man (name sons daugters))

From Unit 1:

rec-data-mfcs

Defining functions on, and reasoning about, Recursive/Structural Data Types with cases/pattern matching <-> Structural Induction proofs:

From Standard ML:

fun match(v: valu, p: pattern): (string * valu) list option =
    case (v, p) of
      (_, Wildcard)               => SOME []
    | (_, Variable str)           => SOME [(str, v)]
    | (Unit, UnitP)               => SOME []
    | (Const i, ConstP j)         => if i = j then SOME [] else NONE
    | (Tuple vlist, TupleP plist) =>
        if   List.length vlist = List.length plist
        then all_answers match (ListPair.zip(vlist, plist))
        else NONE
    | (Constructor(s1, v), ConstructorP(s2, p)) =>
        if   s1 = s2
        then match(v, p)
        else NONE
    | (_, _) => NONE

From How to Code: Complex Data:

rec-data-racket

From Unit 1: Recursive Data Types and Structural Induction (notice literally the same word "Constructor" is used like in Standard ML):

rec-data-function

We can prove the correctness of these functions (we can do the same in Racket/SML):

struct-induct-proof

Recursion on Nonnegative integers:

This is from How to Code: Simple Data (Racket)

;; Natural is one of:
;;  - 0
;;  - (add1 Natural)
;; interp. a natural number
(define N0 0)         ;0
(define N1 (add1 N0)) ;1
(define N2 (add1 N1)) ;2

(define (fn-for-natural n)
  (cond [(zero? n) (...)]
        [else
         (... n   ;template rules don't put this in
              ;   ;but it seems to be used a lot so
              ;   ;we added it
              (fn-for-natural (sub1 n)))]))

From Unit 1 (notice the exact same data definition):

nats

"Termination arguments" for generative recursion (fractals) <-> Proofs by (Normal or Strong) Induction, or the Well-Ordering Principle

From How to Code: Complex Data:

; Termination Argument:
;   trivial case: w <= CUTOFF
;   reduction step: (/ (- w (* r w)) 2)
;   argument: as long as CUTOFF is > 0, and 0 <= r < 1, repeatedly
;   multiplying w by r (the reduction step) will reduce w to eventually reach
;   the base case.

No specific screenshot for this one from the textbook, these kind of arguments are covered in Unit 1.

Recursive code (in general) reducing the problem to a subproblem of 1 size smaller <-> the Induction Step `P(n) => P(n+1)` in an Induction proof:

From Standard ML and Racket:

(*  returns nth string in list
 *  Assumes list is nonempty and n >= 1  *)
fun get_nth(strlist: string list, n: int): string =
    if   n = 1
    then hd strlist
    else get_nth(tl strlist, n - 1)

;; ListOfNumber is one of:
;;  - empty
;;  - (cons Number ListOfNumber)
;; interp. each number in the list is an owl weight in ounces
(define LON1 empty)
(define LON2 (cons 60 (cons 42 empty)))

(define (fn-for-lon lon)
  (cond [(empty? lon) (...)]
        [else
         (... (first lon)
              (fn-for-lon (rest lon)))]))

From Unit 1:

ind

And many, many more...

I'm sure there are so many more matches between Math for CS and Core Programming that I could not think of (or would not fit here without the list getting too long...).

Why will taking Unit 1: Proofs of Math for CS help this situation?

It teaches: Introduction to proofs, Proof methods, Well ordering principle, Logic & propositions, Quantifiers & predicate logic, Sets, Binary Relations, Induction, Strong induction, State machines and invariants, Recursive definitions, Infinite sets.

These are a cohesive whole of fundamental mathematical ideas. They finish off a well-rounded introduction to the mathematical ideas underpinning all of computer science.

When it's time to take these courses, learners do not yet have the mental patterns and the strong logical rigor needed to reason about the mentioned issues. Instead their approach devolves into: guess something, type on the keyboard, run the code, and hope it works, or get some quick feedback, or peek at solutions. Very different than writing a proof by hand, with pencil and paper, which forces you to think hard and form brain patterns. Instead of following code execution, proofs force you to think structurally.

My experience tutoring on Discord tells me that this trial-and-error makes it possible to somehow muddle through the courses and solve the problems, without the concepts ever fully clicking in learners' minds. This is exemplified by the learners who finished HtC but still don't feel like they understood it, when they successfully solve a hard exercise in PLA. Learners finish in a state not quite able to reason about the correctness of recursive code.

I believe learning basic logic, proofs, and most importantly Mathematical Induction and Recursive Definitions BEFORE these courses will greatly alleviate these issues, if not completely solve it.

Advantages of the Proposal:

Learners will gain confidence and start to overcome their math fears early on.
No additional content! Math for CS is required anyway.
It will partly help with the issue that many learners prefer to avoid or postpone math as far as possible.
Learners will have a significantly easier time with the mentioned concepts in the next 4 courses.

Disadvantages

Putting part of Math for CS so early will intimidate people and scare them away from the curriculum.

I believe the opposite will happen: the first advantage I mentioned above. However I can certainly see some running away just from a glimpse, or simply skip over it. I think I'm fine with that; this is a hard, serious academic curriculum after all! I simply have to trust that learners will do things in the order we lay out for them.

Splitting the completion of Math for CS into two will create confusion and a feeling of incompleteness. Learners might decide to go ahead and try to finish all of Math for CS, but the later parts require Calculus. This will take too much time and derail learners from coding.

This is certainly a legitimate concern. However: 1) all of Calculus + Math for CS is required anyway; 2) I still think it will be an advantage. Unit 1 is fairly short and self-contained, and extremely high in value because the logic/proof skills apply to literally everything (that's why it's Unit 1, not Unit 2, 3 or later). Learners can continue from Unit 2 and onward when they reach the point.

Unit 1 does not address the issues with Graphs, Trees, and Algorithmic Complexity.

This is true, however I'd like to keep the changes to a self-contained minimum. If you feel strongly about this, I listed an alternative to move all of Core Math ahead of Core CS.

Appendix (optional):

Details about recursion

This part is optional, you don't have to read it.

It doesn't help that the default, widespread code learning method is imperative, which is what almost all learners encounter as their first programming experience. Learners I've talked to often say that they "go down the rabbit hole" of following the chain of recursive calls all the way down, because they treat the code in an imperative way, they keep following "the next instruction". They also have trouble with the idea of a "suspended" recursive call, how return values from recursive sub-calls are passed "up" to the main call. This is borne both in my experience and in the research.

Quite often learners refuse to believe that a recursive function is correct. They feel like they've been lied to, or they've been cheated or fooled somehow. Instead they follow the recursive calls all the way to the base case and get lost somewhere due to the huge mental memory requirement. Even when they succeed, not much difference. It doesn't "click". In the next recursion exercise they have to repeat going all the way down again. Even if they succeed without following the calls, they are surprised and unsure what they did right.

Learners cannot see that the problem is self-similar, that the smaller subproblem has the exact same pattern as the larger problem, how solving the smaller subproblem leads to a solution for the bigger problem, and that they should simply assume that the function returns the correct result on the subproblem and go from there.

This is our good old friend... (drum roll)... Mathematical Induction!

Intuitively, my thoughts immediately went to learners' lack of experience writing mathematical induction proofs. Recursion is simply induction in code form. In my investigation I came across a 1986 book called Thinking Recursively, specifically aimed at explaining recursion and helping with its common difficulties; which, after a brief casual introductory chapter, starts off immediately with mathematical induction. So it's not just me.

When we normally write an induction proof, we start with the base case of some statement: P(0). Then for the induction step we ASSUME P(n) is true (humans have a lot of trouble even with this!), and prove P(n+1). Infinitely many statements are proven correct like falling dominoes: P(0) is true, it implies P(1) is true, which implies P(2) is true... This is in line with the general, chronological, forward, past-to-future thinking of humans.

The assumption of P(n) corresponds to what Greg Kiczales in How to Code means by "trust the natural recursion".

It doesn't help that recursion in code forces you to consider this implication IN REVERSE. In code, you try to write the P(n+1) step first, then reduce it to P(n) by a recursive call to the same function. Why should that work? Because it depends on P(n-1). Why should that work... It's like the mental rug being pulled out from under you. It just doesn't "click". With induction the assumption is reversed (at least in our minds).

Common complaints and experiences

This part is optional, you don't have to read it.

Some learners express this feeling of "not making progress" or "understanding what they did right" especially after successfully completing a hard recursion exercise, or even a course.

"I've done the How to Code courses, but I don't know if they worked out for me."
"I got a 'All 20 test passed!', so thanks! I do still have difficulty understanding what I did exactly..."
"I've made it this far (to PLB), I've spent months but I'm not improving at all."
"I'm so tired of getting stuck on each problem for hours. I just want to move on." (hey I've been there!)
"I'm just gonna get through this material quickly, or skip it if it takes too much time."
"Who cares about these languages anyway? Why should I even use recursion? I'm not convinced."
"After all this SML/Racket crap, ..."
i did do htc but i struggled with it a lot, i didnt want to waste time so i moved on with intent to revisit it, i saw how valuable the course was...
"this class almost made me quit OSSU after i forced myself to do the first part, so i skipped the second one"
I've been stuck on this course for so long, I've read the comments and I understand it should be done but I really can't focus on it. I tried using the book instead too, but it feels like dragging myself through mud.
Every time I tried to think about all the steps in a list with more than 2 items, my head just explode.
With more simple problems I can imagine all the calls and the stack being build and returning values, but for this problem in particular, no way! its normal or I am missing something?

Some resources on recursion

Reality is that most the people you describe are ngmi through the course no matter what, whether they're introduced to these topics in math or programming. These courses are already pretty gentle introduction; it's a class that someone aiming for a Bachelor's in CS should not be struggling in. If an intro course filters you out you change majors right?

@romanbird Sorry I don't know what "ngmi" means. English would be appreciated.

These courses are already pretty gentle introduction

Definitely not! Most people are completely alien to these concepts. Many learners do quite well until they reach either How to Code Complex, or Prog Langs Part A, where they face a huge wall in front of them all of a sudden. I think these people have potential (they're not stupid or making a half-assed effort), but they don't know what to do, where these concepts came from, or where/how to learn them, and feel helpless. The programming languages greatly obscure the concepts behind the syntax.

I think that U. of British Columbia (How to Code), MIT (Intro Prog & CS with Python), U. of Washington (Prog Langs ABC) teach these topics in a separate Math course to first and second year students already, before these courses, or concurrently with these courses. If this is the case, then we should too. Otherwise, they do not provide a gentle introduction to these topics at all.

it's a class that someone aiming for a Bachelor's in CS should not be struggling in

"Should" is not what happens in the real world unfortunately. According to the educational research and many blog discussions above, a lot of Computer Science majors, graduates, and even people with many years in the industry struggle with them. The common denominator is lack of solid foundations in mathematical concepts. We are not a university so we might be able to do better.

If an intro course filters you out you change majors right?

That's a bit harsh, I think. In my country at least, you have to pick a major before enrolling, and you must stick with it. (This "filtering" is also part of the ruthless business practices at many universities, I taught at one for 10 years. Bu let's stay on topic.) According to some commenters in Discord (it was Alaharon I think) currently some universities they are attending do a very poor job of teaching logic and proofs. Again, we are not a university so sometimes we can do better.

I do not believe it's a person-specific issue. As I mentioned above, even learners who succeeded in these courses and liked them, struggled quite a lot and sometimes could not shake the feeling that the concepts did not settle quite right in their minds. In the best case it greatly extended their time to complete the courses (I remember a few learners who took 4-6 months of honest, good-faith effort on the two How to Code courses).

So, if I didn't make it clear in my post, I believe that the proposal will benefit everyone including the finishers, not just those who struggle and drop out.

I was able to steer a few struggling learners on Discord to learn the math first, and we got really good results. I don't have solid data to back this up (it's just anecdotal at this point) but I believe it.

Two more experiences happened just yesterday/today (Oct 30, 2022):

(About mutual reference in How to Code: Complex Data) "So maybe I'm stupid somehow, but I'm sure I'm not that stupid to miss it all ... Literally I understood nothing. Specifically the loe function. ...(later) It's like I should learn (Math / HtC / PLA) in some sort of order, but idk how."
(about Towers of Hanoi in the MIT course) "I feel like I'm too dumb for this course. I have been trying to understand the towers of hanoi for literally two hours going line by line in python tutor. In the lecture he was just like yep here it is! easy! feels like an absolute waste of time if it's just not clicking. I will try but I don't know how I'm going to get through this course if I have to pause to understand something for two hours each time a concept is brought up. It's taking me like 2 weeks to make it through 2 lectures and by the time I get to the next I just forget all the stuff I've done previously."

(Again, these learners are definitely not "too dumb for this course", they just don't know what to do or how to proceed.)

I'm really curious about the hypothesis presented in this issue. I wish we can do some "experiments" with the people who are struggling and see if they can get through it afterwards.

I always had a more cynical mindset that some people just won't understand it, no matter what. I would like to see if this sapproach (i guess assuming they really understood the fundamentals of logic) will correspond to them doing better in those type of programming problems.

I always had a more cynical mindset that some people just won't understand it, no matter what.

Trust me, I'm struggling to stave off the cynicism every day :sweat_smile: But I've seen some seemingly hopeless cases have 180 degree turn arounds, so I believe it can be done with better teaching/learning.

The hypothesis itself is a no-brainer for me, I believe it's so obvious (and tried to show it with the screenshots), but it's very difficult to convince others. The rest of the hypothesis comes from some of the literature and books written to tackle the same issues. (For example this book starts right off with induction proofs.)

I've done a bit of "experimenting" with 2-3 learners on Discord with fairly good results. (I think there was also a "Logic First" type of educational movement in the 1990s in the US but it didn't catch on.) I'd be willing to extend the RFC if there are volunteer "guinea pigs" :smile:

There's a real problem identified, and a proposed intervention. The intervention is relatively light (reordering 1 module from 1 class) and would be easily reversible in the future. I agree with @angle943 that it would be good to be able to assign students to random treatment groups (some take the current track and others take the proposed track and we compare them side by side). But that has distinct overhead and isn't very suited to our current setup (static github course list). Also comparing 2022 students who took the current track with 2023 students who take the modified track is a reasonable comparison.

So far I would summarize the objections to this RFC as, "Yes, the problem identified is a true issue (students struggle with these issues) but maybe there's nothing that we can do." I don't agree with such a framework. Given the proper structuring of learning materials, the proper interventions to student difficulties, there's nothing in the CS curriculum that we should see as impossible for dedicated students to learn.

I'm happy to try out this intervention. The RFC points out the potential disadvantages that I see. I think these are reasonable to take on in order to help students succeed in Core CS.

I'm interested if others have other proposals that would address the problems identified in this RFC, or see other disadvantages in the proposal here. Please do share.

Hello Spam! Thank you for making a detailed proposal. I would like to provide my thoughts on this from my own experience as an OSSU student.

First to give some background:

I started OSSU in 2019 and I'm done with most of the courses in core (the big things still left are Operating systems, networking, and algorithms). I finished core programming in 2020 back when there were also the software construction courses in it. Prior to the OSSU, I studied java in high school, but had never come across the concept of recursion. I had not touched math (outside of the realm of finance and accounting) in the many years prior to 2019 (when I started the OSSU).

My experience: I do not relate the problem being proposed.

The two HtC courses - I breezed though them like they were nothing. Didn't find a single hard thing. The big issue I found with them is that they were a huge drag - very boring. I don't enjoy writing so many parenthesis and my brain naturally moves towards iterations and variables. Nevertheless I persisted and got it done. They weren't hard, they were just a slog.

PLABC - These courses are a lot of fun (even though I don't like emacs, I was happy to come across it). I did this after I had done a lot of the other courses in the OSSU (eg. Nand2Tetris, CS50) which I believe made PLABC much more understandable and relatable. I believe the OSSU is making a mistake when it recommends HtC as a prerequisite to PLABC. PLABC is much harder and requires more coding experience and maturity to appreciate the topic.

I think the experience I gained using python (dynamic) in Nand2Tetris, Java (static) in high school, C (low level and has pointers and mutation) in in CS50 and Racket (functional and immutable) in HtC helped me understand and appreciate the value of this course.

I do not think a student who has not programmed in various paradigms and languages can get nearly as much PLABC as a student who has.

Comments:

On the surface it looks like recursion is the true mastermind criminal here, but it's not. It's a general lack of exposure to the underlying abstract mathematical concepts: logic, proofs, reasoning, induction, recursive definitions and how to reason about them using (normal or Structural) Induction.

I do not believe the exposure to abstract mathematical concepts is the culprit here. At least it wasn't in my case. I hadn't come across these topics until after I had already finished core programming, and I didn't find a single difficult thing in core programming provided I spent some time actually thinking and understanding everything instead of skipping and moving forward.

On Math for CS:

I'm done with some units from Math for CS. I went above and beyond. I solved every single problem in the textbook. Took me hundreds of hours. It's an order of magnitude of work and difficulty above core programming.

If someone is struggling with core programming, they are going to have a real real hard time with Math for CS. They will think "this CS stuff is too hard for me" and quit. I would have likely done so if I did math for CS before core programming.

In fact, I tried. Back in 2019, I picked up Math for CS and found it to be "much ado about nothing" as a told my friend. It was not only somewhat mindbending, but I also wondered why knowing how to prove the square root of 2 being irrational was going to be useful to me. So I dropped it and did core programming instead. There were other courses that tried to teach things like induction in the curriculum (LAFF - Linear Algebra foundations to frontiers which is now gone from the curriculum, replaced by Gilbert Strang) and I didn't get the point of it back then as well.

I only came back to math for CS this year (2022) and I appreciate the concepts far more because of my experience with the other courses.

Rationale for Proposal

This rationale actually worked in the opposite way for me. I got interested in doing Math for CS because it modeled what I learned in the programming courses, not the other way around. (Remember I first came to the OSSU for the computer stuff, not the math proofs stuff. )

Not just appreciation, but also the discipline to sit through the courses. The math ones are harder to finish than the coding ones because coding is "more fun" (at least to me).

I do not think moving math for CS to the top of the OSSU will bring much benefit (as it requires some coding/educational maturity) and is just too damn difficult/intimidating/long for a newbie.

I think it will just produce a lot of dropouts.

Advantages of the Proposal: Learners will gain confidence and start to overcome their math fears early on.

I think it will do the opposite (or maybe I am projecting) - it will make them afraid of math and computer science. The Math for CS material does not hold your hand at all and are much harder than other parts of the curriculum.

I am also concerned that the students will not be able to understand most of the "good conclusions" we reach at the ends of the proofs section of Math for CS - the halting problem, why it's impossible to build a type checker, etc. (I didn't even know what a type checker was until I finished PLABC).

Putting part of Math for CS so early will intimidate people and scare them away from the curriculum.

I think this disadvantage vastly outweighs any benefits we gain from putting math for CS at the top. We must remember that we are not in a university where students are forced though the curriculum. Everyone here is mostly by themselves. It is important for us to manage the students motivation and confidence level and smacking them with Math for CS on day 1 is probably not what we wont to do.

Other notes:

Note 1:

In the math for CS lectures, the professor mentions that some MIT students never really understand induction.

https://www.youtube.com/watch?time_continue=385&v=K8ZfzNN1miQ

Go to the 5:30 mark.

"So finally, we come to a pedagogical question about, why is it that in 6042 we taught well-ordering and principal first, in fact, the second lecture, and are only now at the end of third week getting to the induction principle, which is much more familiar, and people argue they like it better, at least most of them.

Well, the answer is it's a pedagogical strategy. And it's one, in fact, which the authors disagree with, not united on. My view is that we're better off doing well-ordering principles first.

And the reason is that our impression from conversations with students, and surveys, and from exam performance shows that only about 80% [correction] of the students get induction no matter how hard we try to explain and teach it. They report worrying about things about that assuming P of n to prove p of n plus 1 is somehow circular.

And it's certainly measurable that 20% or so of the class just can't reliably do proofs by induction. Now this baffles the 80% to whom it's obvious and who know how to do it easily. And it baffles us instructors. We can't figure out what the problem is that those 20% have. And we've been trying to teach induction lots of different ways."

It could just be that 20% of people can't get induction (and thus probably recursion) no matter how you teach it - whether you move math to the top or not. And what you're seeing on the discord is selection bias of those 20%.

Note 2:

Reality is that most the people you describe are ngmi through the course no matter what, whether they're introduced to these topics in math or programming. These courses are already pretty gentle introduction; it's a class that someone aiming for a Bachelor's in CS should not be struggling in.

I agree with this. HtC is based on the book HtDP which is already one of the simplest books on the topic (a harder alternative being SICP). I agree that if a student is struggling with these they are likely NGMI and should learn something like software engineering or web development instead and come back when they have more programming experience.

That said, this is strictly my opinion (which I hold because I found core programming to really easy).

For example,

(about Towers of Hanoi in the MIT course) "I feel like I'm too dumb for this course. I have been trying to understand the towers of hanoi for literally two hours going line by line in python tutor. In the lecture he was just like yep here it is! easy! feels like an absolute waste of time if it's just not clicking. I will try but I don't know how I'm going to get through this course if I have to pause to understand something for two hours each time a concept is brought up. It's taking me like 2 weeks to make it through 2 lectures and by the time I get to the next I just forget all the stuff I've done previously."

I finished this course in a week. Did 1 week of material per day after work. I found this course to be extremely easy and it actually pushed me to the top of dunning-kruger.

these learners are definitely not "too dumb for this course"

I don't know. My first instinct kind of makes me conclude that they could be (not trying to be rude) ... or it could also be a lack of initiation into certain ways of thinking (as the OP believes)? I don't believe they are "dumb" in the strict sense as dumb people do not spend their time trying to self learn academic things on the internet, but the intro MIT course is objectively easy someone struggling with it either needs more programming experience from other places ... or could just be "too dumb for this course" (again, not trying to be rude - just trying to analyze the problem).

They could just be too dumb for recursion, which is not bad company - I know tons of AI/ML engineers in SV who are extremely bright (one has a PhD) and have never used functional programming before. Some concepts are just harder for some people for unknown reasons.

We are at the boundaries of what you can do with MOOC style online self-learning where you have to cater to "the general student" and not special cases who might have trouble with certain topics.

Conclusion:

I would say we should do something like this:

1) Change the prerequisite of PLABC to "How to Code, CS50, Nand2Tetris, and optionally, basic Java." 2) Encourage students who have trouble with recursion to produce dry runs on paper to see how all the variables change and how there is some condition that produces termination. 3) I am not against mentioning a quick note above core programming which says that students struggling with recursion are encouraged to go though the first 7 chapters of Math for CS. (Not chapter 8 because it contains the Halting Problem.) 4) We can direct them to an optional course that helps them with recursion.

Thanks for the detailed response! Here are my thoughts. I hope it doesn't come off too offensive.

My experience: I do not relate the problem being proposed.

That's great! Indeed, there are many learners like yourself.

I did this after I had done a lot of the other courses in the OSSU (eg. Nand2Tetris, CS50)

It seems like you've gone in reverse order. Of course, going through the later, harder courses first will make HtC/PLABC easier. Especially Nand2Tetris, which uses everything taught in earlier courses. I don't think your unusual order of doing things is a typical experience. There were some learners who jumped ahead and tried to do Nand2Tetris before Core Programming, and they failed (some of them quit).

I believe the OSSU is making a mistake when it recommends HtC as a prerequisite to PLABC. PLABC is much harder and requires more coding experience and maturity to appreciate the topic.

I think it makes sense to have it that way. PLB uses Racket, and both PLA and PLB use functional programming, recursion and recursive data types. As such, I think How to Code is a very good preparation for PLABC.

I do not think a student who has not programmed in various paradigms and languages can get nearly as much PLABC as a student who has.

Sorry, I really don't follow. The main purpose of PLABC is to make the student program in various paradigms. Again your brain seems to prefer the reverse order. (No offense! Some people are like that I guess.)

I didn't find a single difficult thing in core programming provided I spent some time actually thinking and understanding everything instead of skipping and moving forward.

That's great again, but as I mentioned above, learners struggling with these concepts don't even know what/how to think about them, or even how to describe what they are struggling with.. It's like being in a foreign country without knowing a single word of the language.

If someone is struggling with core programming, they are going to have a real real hard time with Math for CS. They will think "this CS stuff is too hard for me" and quit. I would have likely done so if I did math for CS before core programming.

We are asking you to do only Unit 1. Not all of Math for CS. I believe I made a convincing case that it teaches the same concepts as Core Programming (some of them are quite literally the same). Why is one considered so much harder than the other? They are the same concepts. Please someone answer this question. Why?

...There were other courses that tried to teach things like induction in the curriculum...

Unfortunately many programming courses really suck at teaching these topics. Because the programming world treats them too informally and "hand-wavy", don't want to spend too much time on math, and assume that you just "get it". That's why learners express their frustrations with "trust the natural recursion!" and "prove it for the base case, then prove it for the induction case" explanations in How to Code and MIT Intro to Prog/CS. To them it feels like a back-handed insult. From years of teaching experience, I know that students feel insulted when they feel like they are supposed to know something they were never taught.

I think my proposal addresses this. When learners see the exact same ideas directly used in Core Programming, they will see the point much more easily. They will also feel a lot less frustrated with the "hand-wavy" explanations given in the programming courses, because they will learn it properly first.

and I didn't get the point of it back then as well.

I keep seeing this issue. Why are younger learners so incredibly impatient? If they don't see the point of something immediately, they reject it outright. Often in life we have to do things without immediately getting the point, because it takes time. We can trust the teachers, the topics, the community and the history of it, instead of questioning, opposing or abandoning it. Whatever happened to that? I had to suggest this little mentality change to some learners on Discord and they thanked me later. Is it because of the age of instant gratification? (Like, people don't even have enough time to type words, so they use things like "ngmi".)

I got interested in doing Math for CS because it modeled what I learned in the programming courses, not the other way around.

I agree that Unit 1 models Core Programming, not the other way around! That's why it's called "Mathematics for Computer Science" and not "Computer Science for Mathematics". The purpose of Math for CS is to prepare CS students with the mathematical ideas they will face in CS.

So once again I don't get what you're saying, your brain seems to prefer things in reverse order.

I believe that the model comes first. The learners I'm describing here are suffering exactly from this problem: they don't have even a clue about the mental model required to tackle these concepts. Because THEY NEVER LEARNED THEM BEFORE! Not their fault (this is why I don't accept the "they won't make it" explanations). Learning the model first would help them a lot.

Not just appreciation, but also the discipline to sit through the courses. The math ones are harder to finish than the coding ones because coding is "more fun" (at least to me).

You said above you didn't like How to Code, but persevered. These learners do not find How to Code / PLAB fun either. (A few of them said they enjoy math more.) I don't think I can do anything about people's individual discipline or enjoyment levels; however I'd say that the later/more advanced courses which you did first, such as CS50/Nand2Tetris, require far more discipline. Especially Nand2Tetris, which is a total monster compared to Core Programming.

Again, you are in reverse for some reason... do the much harder thing first, then do the easier thing later... I don't get it. (No offense)

I do not think moving math for CS to the top of the OSSU will bring much benefit (as it requires some coding/educational maturity) and is just too damn difficult/intimidating/long for a newbie.

I don't believe this is true. Unit 1 is not that long. It does not require coding (millions of people learned it before coding even existed). Some of the exercises in Unit 1 are about programming concepts from a math perspective, but at the Intro CS level, and they define everything from scratch without relying on prior knowledge.

Unit 1 and Core Programming cover many of the same concepts as I argued in my post. Why is math "too damn difficult/intimidating/long" but programming isn't? It doesn't make sense. I can only conclude it's a cultural issue about all the fear around math.

The Math for CS material does not hold your hand at all and are much harder than other parts of the curriculum.

I don't think Core Programming holds your hand either, otherwise I would not be mentioning these learners' experiences (I don't think they considered those courses to hold their hands). Moreover I believe I have greatly alleviated Math for CS difficulties by spending several months writing long, detailed solutions.

I think it will do the opposite (or maybe I am projecting) - it will make them afraid of math and computer science.

I like to believe in the learners. I think most of the math fear is cultural, so they just keep avoiding it. Avoiding and postponing it builds up the fear even more. If they get exposed to math earlier it will be less scary. ALSO IT'S JUST ONE UNIT.

It is important for us to manage the students motivation and confidence level and smacking them with Math for CS on day 1 is probably not what we wont to do.

This assumes that math is demotivating (and "smacking them") by default, which I do not accept. Moreover the learners I described got demotivated because of Core Programming courses, not because of math. They didn't even reach the math courses. I hope that's clear. My proposal is not on day 1 (it's after Intro CS), and once again it's only Unit 1.

They report worrying about things about that assuming P of n to prove p of n plus 1 is somehow circular.

This is not related to induction itself, but related to the overall issue humans have with proving a statement involving the "material conditional:" if A then B. Humans struggle a lot with just assuming A, there is some research about this. Because they think A is not justified. I mentioned this in my post above. Their approach of Well-Ordering Principle is a proof-by-contradiction wrapped around a normal-induction-proof. Proof by contradiction is another example of reverse thinking.

It could just be that 20% of people can't get induction (and thus probably recursion) no matter how you teach it - whether you move math to the top or not. And what you're seeing on the discord is selection bias of those 20%.

First it is just a hypothesis that they "can't" get induction no matter what. My proposal is also a hypothesis, although I think my hypothesis is much more logical and reasonable. Who are we to assume that someone "can't" get something?

Second, the learners I'm talking about never learned induction or recursion. How to Code does not teach recursion, it throws you into the code and says "trust the natural recursion". You're supposed to figure it out on-the-go. Some learners make it out OK, but many learners said they don't even know what "natural recursion" means. (PLEASE, I WANT YOU TO THINK ABOUT THAT.) Then they try to read the code imperatively, which clearly shows they don't know induction or recursion. How are we concluding that these people "can't" get induction no matter what?

Once again: my point (which I hope was not misunderstood) is that the learners were never given a chance to learn these mathematical concepts, and the Core Programming courses do not teach them well.

My proposal says: "let's give these people a chance to learn induction/recursion FIRST".

HtC is based on the book HtDP which is already one of the simplest books on the topic (a harder alternative being SICP).

The fact that it's a simple book doesn't mean that it does a good job of teaching the topics in Unit 1. The "simplicity" is achieved by sweeping the mathematical understanding under the rug. The book teaches how to design functions by using structural induction on recursive data, without explaining what it is. At first it's OK, but later with mutual reference and mutual recursion it can get nightmarish if you don't have the reasoning and proof skills. (This is part of a general pattern in the programming world, of "teaching math without teaching math by hiding it under the rug.")

I agree that if a student is struggling with these they are likely NGMI and should learn something like software engineering or web development instead and come back when they have more programming experience.

Once again I don't know what NGMI means, and I really don't get this argument. If someone has trouble with math, induction, recursion, logic, reasoning, how is getting experience in software engineering and web development going to help? How long is this "go away and come back to Core Programming and math later" period supposed to be? 1 year? 2 years? 10? I suppose many people would never come back. Secretly skipping math, only to suffer later in Core Theory. This seems to be a self-perpetuating problem of avoiding and fearing math in programming culture.

When learners suggest getting bored from, or stuck on, a programming course, we usually recommend doing math alongside. Why can't they "go away for a while" to do math, and come back to do programming? Why is math the "hard thing by default" and programming "the easy thing by default" when they cover the same concepts (as I argued in my post)? Nobody really seems to have an answer to this. For some reason math is just designated to be "the hard thing you must fear." Although for decades people learned math just fine, because programming didn't even exist back then.

I finished this course in a week.

So did I, but we're not talking about you and me.

but the intro MIT course is objectively easy

I don't think so. Some learners struggle with other parts of that course as well, not just recursion, for similar reasons. They struggle with the Algorithmic Complexity parts (again due to lack of math and somewhat poor/quick explanations) and with the OOP parts (this is less of an issue).

Change the prerequisite of PLABC to "How to Code, CS50, Nand2Tetris, and optionally, basic Java."

CS50 was removed, How to Code comes right before PLABC, Java is right after it.

I cannot agree with the Nand2Tetris suggestion. Nand2Tetris is far more difficult and time consuming than anything that comes before. Plus it's not part of Core Programming, it's in Core Systems. Nand2Tetris uses everything that comes before. It requires a solid understanding of how programming languages work, because you're supposed to write an assembler, a VM translator and a compiler. You need to process one language with code you write in another language. It also requires OOP because Jack is object-oriented. PLABC prepares for all of this.

Again I cannot make any sense of the strange reverse order in which you did things. I'm happy it worked out for you, but that is exceedingly rare.

The rest of your suggestions are about recursion, but as I made clear in my post, recursion is not the core issue. There are other issues: logic and reasoning skills, structural thinking, structural induction on recursive data types (base cases + constructor cases), and more.

Encourage students who have trouble with recursion to produce dry runs on paper to see how all the variables change and how there is some condition that produces termination.

This is OK as a suggestion and definitely somewhat helpful, but not too much. It's difficult to do when mutual recursion is involved (even with Dr Racket's stepper). Learners reported that "every single time I have to write down and go through the call stack." The issue is that this does not change the learner's thinking away from imperative thinking. So they become prisoners of stack-following. As I mentioned in my post, recursive-stack-following is reverse-thinking, whereas induction is forward-thinking which is much easier for humans.

The other issue is that, following the calls to see that a base case is reached does not help learners see the self-similar structure of the problem, and the problem-subproblem connection that is needed to solve it (example: the string permutation problem in the OCW MIT Python course that trips up everyone). They don't understand how to obtain a solution to the one-size-bigger problem by taking the solution to the one-size-smaller problem and changing it. So it looks like "recursion magic" to them.

I hope it doesn't come off too offensive.

Don't worry about it. You've added a lot to the curriculum and helped a lot of students out. Your views are always respected, encouraged, and considered. I am also a very hard person to offend..

It seems like you've gone in reverse order. Of course, going through the later, harder courses first will make HtC/PLABC easier. Especially Nand2Tetris, which uses everything taught in earlier courses.

It's not a reverse order. The OSSU says:

For simplicity, we recommend working through courses (especially Core CS) in order from top to bottom, as they have already been topologically sorted by their prerequisites.

From what I understand, you can go any order you want, provided you meet the pre-requisites. The top to bottom order is just for simplicity. Otherwise what is the prerequisite column there for?

I don't think your unusual order of doing things is a typical experience.

I don't know. I'd be happy to hear more student's experience here. I found that jumping around the introduction of different topics kept things fresh and prevented burnout. Eg. I did some core programming, them some core math, then some core applications, and then back to core programming, and so on. After all, for how long can you study one subtopic before you start wanting a change?

I do believe that this flexibility is a standard part of online education, and if not - then it is something to be strived for.

I think it makes sense to have it that way. PLB uses Racket, and both PLA and PLB use functional programming, recursion and recursive data types. As such, I think How to Code is a very good preparation for PLABC. The main purpose of PLABC is to make the student program in various paradigms.

I found it to be a course about programming languages, and not a course designed to teach you a language. You get much more from this course if you've used the paradigms before.

It seems premature to ask a beginner who has only done an intro course and HtC to take this course. As I said earlier, I'm only providing my experience as an OSSU student. I've never taught math and don't hang around the discord much.

In your support, the instructor says:

That the way I've designed the material assumes you have done programming before just in different languages. It doesn't have to be a lot of programming however. If you've taken one or two other programming courses and succeeded at them. This will probably be fine. It doesn't have to have been courses. You could have picked it up on the job or on your own learning or whatever. On the other hand this is not an advanced programming language course. I typically teach this on campus to sort of second year students, not people with years of professional industry experience or not even what I would consider last year undergraduate course. So it's not an introductory course, you should have programmed before, but it's not a particularly advanced course.

So by the instructor, HtC and Intro to CS should be fine. However, I strongly believe that I got much more from this course because I had actually used the other paradigms before and wasn't coming across them for the first time.

Change the prerequisite of PLABC to "How to Code, CS50, Nand2Tetris, and optionally, basic Java."

Before of those reasons, I suggest this change.

CS50 was removed

I am aware. I do think removing CS50 was for the worse, but that's for another RFC.

I cannot agree with the Nand2Tetris suggestion. Nand2Tetris is far more difficult and time consuming than anything that comes before.

I found Nand2Tetris to be far easier than PLABC. PLABC requires some mind bending thinking with streams, promises, currying, etc. and has some challenging assignments, while Nand2Tetris is a very straightforward hand-holdy course where the instructors do all the hard work for you (for example, they give you the signatures of all the functions you will require and leave you to just implement them).

It also requires OOP because Jack is object-oriented.

I don't remember exactly because I did Nand2Tetris in 2019 but jack was very similar to python/java? If you know how to use either, you should be fine.

The rest of your suggestions are about recursion, but as I made clear in my post, recursion is not the core issue. There are other issues: logic and reasoning skills, structural thinking, structural induction on recursive data types (base cases + constructor cases), and more.

I don't agree with this from my experience. I knew almost no logic/induction and I completely breezed through the courses just fine.

I would be interested in studying what percentage of students actually face this issue. If it's something small like 5-10%, then I do not think the curriculum change is warranted and a quick note should suffice like I said here:

I am not against mentioning a quick note above core programming which says that students struggling with recursion are encouraged to go though the first 7 chapters of Math for CS. (Not chapter 8 because it contains the Halting Problem.)

If a higher number of students are facing this issue (say 15% or more) then I change of this sort should be considered.

I am trying to be cautious to selection bias where for example:

Say there are 5000 students taking the OSSU in a year. Only 5% of students (250) face trouble how you are describing it. Say 60% of the students who have a problem (150) hit up discord. 0% of the ones who don't (4750) hit up discord.

This averages to about 1-2 students every 3 days. That's a lot of support messages and would make a discord operator think there is something seriously wrong with the course, but this is only because he only heard from the 150 students who had a problem, and didn't hear anything from the 4750 who found the course to be perfect.

Now say a curriculum change is made that intimidates 10% of the students who come to the OSSU and are asked to do a tough math module on proofs from the get go. 10% is a reasonable estimate given my own experience with Module 1 of Math for CS and as you say:

most of the math fear is cultural

Secretly skipping math

So by making the change, we lose 500 learners, and by not making the change, we lose only 250.

This is a tradeoff problem and the best solution depends on what percentage of people would be intimidated by putting unit 1 of Math for CS at the top and what percentage of people would be able to do the course if they had done Unit 1 of Math for CS before.

I think the short note solution I mentioned earlier is a fair compromise that benefits everyone.

We can direct them to an optional course that helps them with recursion.

If someone is having real trouble with recursion, we can also link this in the note.

So it could go something like:

If you face issues with understanding recursion and find yourself going through the steppers over and over again, we recommend you to finish the first 7 chapters of Math for CS. We also encourage taking this optional course that helps with recursion

(Note: Chapter 8 should NOT be at the top even though it's a part of unit 1 as it contains the halting problem and the impossibility of perfect type checkers, which is not an intro topic by any stretch of imagination.)

Why is math the "hard thing by default" and programming "the easy thing by default" when they cover the same concepts (as I argued in my post)? Nobody really seems to have an answer to this. For some reason math is just designated to be "the hard thing you must fear."

This assumes that math is demotivating

It really is for many people. Math is not easy and requires a lot of effort and thought that people are not used to putting. I'm not saying this is how things should be. In fact, I believe that the world would be much better if more people were educated in math and the hard sciences. However, we must plan for how the world is, and not how we want it to be.

I am only speculating and would be interested in experimenting and learning the actual numbers, but I would not be surprised if we lose 15-40% of first comers when mathematical proofs is the first thing they are asked to do.

In my opinion (and how it went for me) is that math needs to be motivated. I need to show you why you need to know the math and why you should learn it. If I teach you about arcs, velocity, trigonometry, and calculus, you'll be bored. If I let you play some Angry Birds and show you that by learning arcs, velocity, trigonometry, and calculus, you'll be able to create Angry Birds, you'll be more motivated to learn it.

I do not think this is reverse order. I think it is correct order, especially for online learners because they go though these curriculum alone without co-student peers. Their motivation levels need to be kept high.

Thanks again!

From what I understand, you can go any order you want, provided you meet the pre-requisites. The top to bottom order is just for simplicity.

No, the top-to-bottom order needs to be followed. I think that maybe the Github page does not make this clear enough. I really hate the prerequisites column for this reason. It signals very confusing information.

This is especially true about Nand2Tetris. It seems to be quite popular on the web so it attracts people to our Discord. Many learners like yourself looked at Nand2Tetris and saw that "it has no prerequisites" and jumped straight to it, only to fail miserably. Many learners don't understand that there are so many hidden prerequisites.

I think we need to use a stronger language than "we recommend working through courses (especially Core CS) in order from top to bottom".

So I disagree with the way things currently are.

I found that jumping around the introduction of different topics kept things fresh and prevented burnout.

I'm glad it worked out for you, but many learners who jump around struggle and fail. For those who succeed, it usually adds extra unnecessary struggle.

I found it to be a course about programming languages, and not a course designed to teach you a language.

Yes that's true. The idea is to show all the different paradigms and concepts, so that when you see them later in other languages you'll have an easier time learning them.

You get much more from this course if you've used the paradigms before.

By the time learners reach PLABC (assuming they went in order) they will have programmed imperatively and with OOP in Python, and functionally in Racket.

It seems premature to ask a beginner who has only done an intro course and HtC to take this course.

I don't think so. As I said before, How to Code is a great preparation for PLAB, and the OOP section of the MIT Python course is good preparation for PLC. However I agree that to prepare for PLA, we need the concepts from Unit 1.

So by the instructor, HtC and Intro to CS should be fine.

Yep! That's what we are following.

I found Nand2Tetris to be far easier than PLABC.

I'm sorry, but that's completely crazy. Again I'm happy for you, but this is very unusual. Nand2Tetris uses everything that comes before (as I mentioned in my previous post).

I don't remember exactly because I did Nand2Tetris in 2019 but jack was very similar to python/java? If you know how to use either, you should be fine.

Yes, OOP is covered in MIT Python course, then PLC, then the Object Oriented Design courses, which are all BEFORE Nand2Tetris. People who jump to Nand2Tetris will not know it.

I don't agree with this from my experience. I knew almost no logic/induction and I completely breezed through the courses just fine.

I know. Once again, your experience is very different for some reason. Others cannot breeze through How to Code Complex Data at all (Simple Data is usually fine).

Also it's very strange of you say that "I knew almost no logic/induction", because the Jack compiler has a ridiculous amount of recursion, and the Jack grammar uses mutually recursive data types that are about 20x larger and more complicated than anything covered in How to Code (or Unit 1).

So once again, I don't get you at all.

Anyway, I don't agree with the rest of your post, and I'll just be repeating my earlier points. It's mostly about your opinion of learners and math, and my opinion of learners and math being very different. I don't agree that Unit 1 is much harder than the Core Programming courses, and I don't believe learners should be so scared of it.

My point stands: topics in Unit 1 and Core Programming are almost identical, but Core Programming uses them without teaching them, or sweeps them under the rug, and learners don't understand them.

Thanks again!

Just for reference for those who don't know: this is the massive mutually referential data and massive recursion in the Jack grammar/compiler in Nand2Tetris Part 2 (much more difficult than Core Programming, which prepares you for it): jack-grammar-mr

Also it's very strange of you say that "I knew almost no logic/induction", because the Jack compiler has a ridiculous amount of recursion, and the Jack grammar uses mutually recursive data types that are about 20x larger and more complicated than anything covered in How to Code (or Unit 1).

Yeah that's what I'm telling you. You don't need logic/induction to understand recursion. Recursion is a very easy concept. You know how to solve a small problem, and you know how to make a large problem smaller. Therefore you know how to solve a large problem.

I can see some students struggle with it. I would be interested in figuring what percentage of students do and do not. The MIT instructor (as quoted above) says 20% of people can't seem to get induction. This is very surprising to me.

Recursion is a very easy concept.

For you, maybe. Not for others. Decades of research

You know how to solve a small problem, and you know how to make a large problem smaller. Therefore you know how to solve a large problem.

That's the same as an induction proof. They are the same thing. That's what I'm telling you.

This affirms to me that, once again, recursion is not the core issue, but overall logic and abstract / structural thinking patterns are. You somehow acquired the necessary mental models and thinking patterns elsewhere, on your own, from much harder things. You didn't even realize what you're doing is induction. I guess this is what Prof. Kiczales refers to in one video as "learning by osmosis."

To reiterate my points:

We cannot know if "X% of college students can't learn topic Y". Some researchers claimed the same thing about programming in general but they had to retract that research and were proven wrong. Because this type of reasoning is unjustified and cannot be reproduced. And to be honest it's insulting to assume things like that.
Survey of all research on recursion from 1970s until today does not report such a percentage. It shows that students get it, with different approaches and amounts of time/effort. It does point out the limitations of the research.
Even if Prof. Meyer's informal survey of MIT students was somehow accurate (which it isn't as I show below), it cannot be reproduced and generalized to the rest of the student population.
Those 20% of MIT students said they have a problem with the material conditional (which a lot of humans do, see Peter Smith's book): assuming X to prove Y, because they thought it was "circular reasoning". Not with induction itself. And I know why.
Edit: To prove my point, just today this "circular reasoning" issue happened with a learner, in a simple proof that has nothing to do with induction. It happened in a statement of the form A => A (a logical tautology) which the learner believed was "circular reasoning", because of the common issues humans have with the conditional. The conditional is really the number 1 enemy of humans.
Because they have an issue with Modus Ponens. Induction is an infinite chain of Modus Ponens applications: 1. Prove P(0). 2. Prove P(0) IMPLIES P(1). 3. Use Modus Ponens on 1 and 2 to conclude P(1). 4. Keep repeating with P(2), P(3), .... But because this gets tiring, typically a shortcut is used: 1. Prove P(0). 2. Assume P(n), prove P(n+1). This shortcut makes the Modus Ponens applications implicit, so they have trouble with that. They feel assuming P(n) is not justified. This is common. All it takes is some explanation and some practice to get over that feeling.
If those MIT students were explained this properly, the percentage of students who get induction would be 100%. That's it. There is no such thing as "they can't get it." That's stupid and insulting. Prof. Meyer seems to have taken another approach: teaching Well-Ordering Principle first instead.

@spamegg1 if I understood your comments correctly, it seems some students are having trouble with "underlying abstract mathematical concepts: logic, proofs, reasoning, induction, recursive definitions and how to reason about them using (normal or Structural) Induction.", which is leading to a poor learning experience with the HtC and PLAB courses.

I have not taken the courses HtC, PLAB and MIT's 6.042J yet and I not will suggest replacing them, but the experience you described ("Instead their approach devolves into: guess something, type on the keyboard, run the code, and hope it works, or get some quick feedback, or peek at solutions.") is very familiar to me as I had that experience in CS50 (in the image resize problem I believe) some years ago.

Going against what you said of not suggesting alternatives, while studying "Unit 1: Proofs of Mathematics for Computer Science" might solve the problem, it seems to me that it would be harder to learn the concepts you described from it for a student that isn't used to the style of mathematical books (definitions, theorems, lemma 1, 2, 3, prove this and that, examples, etc.), they may need a more hand-holding approach. It doesn't need to replace it, it could just be an extra resource.

Instead of suggesting going through Unit 1 of MIT's 6.042J, may I recommend you look into the free "Big Ideas in Mathematics for Future Teachers" series of books? I'm studying the first one so far (there are 6), "Number and Operations", I should have finished reading it by the end of the next week's friday and I'm writing a small review for it. It's not a book series designed entirely for self-study, but I found it does work for it with some caveats (which I wrote in my review so far). It doesn't mention normal or structural induction (it does explain "inductive reasoning"), but it did teach me how to think structurally at all, even if at the first couple chapters I got stuck for a long time thinking about how to solve the problems. In other words, it gave me the "necessary mental models and thinking patterns" as I went through the text, or so would I like to think (and I'll only be certain of it if I manage to be successful with both HtC and PLAB I suppose).

Reading your comments, I've thought of an example that illustrates what someone that learned the content of just the first book of the series should be able to do.

In chapter 17 there is a problem called "locker problem", this is what it says:

"The teachers at Read Elementary School play the following game after all the students have gone home. The first teacher opens an entire row of 100 lockers. The next teacher closes every other locker starting with the second locker. The third teacher changes every third locker beginning with the third (If a locker was closed, she opens it, and if it was open, she closes it). The fourth teacher changes every fourth locker starting with the fourth ... and so on. After the 100th teacher has completed her work, which lockers end up open ... and why?"

The "trial-and-error" students that "somehow muddle through the courses" (or as I would call them, "brute-force learners"), would likely try to solve this problem at first by changing the lockers status for every teacher, from the first to the hundredth, either by hand or with the help of a program, whereas a student that has learned to think structually would analyse the problem, describe what is happening, find connections between known information, see what follows from those connections and eventually write a solution via a proof of sorts.

While the locker problem may be doable to a brute-force learner, a problem like the following (it's in Chapter 18 of the same book) would not be easy to solve, maybe it'd be even impossible, as they would need to understand what it is asking too (if and only if requires proving the statement and its converse are both true):

"True or False? A natural number is divisible by 9 if and only if the sum of its digits is divisible by 9. If it is true, prove it. If it is false, find a counterexample".

The authors' stated goal in the book is "We view mathematics as the study of patterns and structures. We want to show you how to reason like a mathematician". I have experienced what is like to think like a mathematician, so I say their books achieve that goal.

It can be quite time consuming in the beginning, specially in the first few chapters, as you're really forced to think deeply and broadly in a way that is very alien for most people, and the book itself is not the usual textbook people are accustomed to (it's an IBL textbook, which I'm biased towards ever since learning about the concept since it suits how I view learning in general), but now I'm averaging 2.5 chapters a day while not studying it full-time.

I hope that adds some value to the discussion. You can find the book series searching for the title, but if I'm allowed to I can post the link here as well. It's from University of Wiscosin and it's free. There are more books like this which I'm interested in but I haven't studied them yet.

@RRock07 Thank you for the extremely thoughtful response. (You've actually read what I wrote carefully and put a lot of thought into it.) I've looked through the books. I don't consider them to be appropriate for this issue; they are aimed at math teachers and contain very few exercises (not well-suited for self-study) and a bit too low-level (elementary/middle school). They are fairly weak in abstraction, and don't tackle these issues (especially logic, proofs, structures) very well. But maybe someone will find them helpful! They will be very useful for me, for sure.

(No offense to you) Honestly I'm getting sick and tired of all these limitations in OSSU, and tired of debating so many different resources, and I'm getting more depressed about this issue. I'm thinking of leaving OSSU and creating my own curriculum from scratch, where I solve these problems once and for all, from the root of it.

As a self-taught software engineer without any formal math education, I dropped out of high school and earned my GED before completing just one year of college with a focus in linguistics. My programming journey began with a boot camp about 10 years ago, where I learned the Ruby language and have been using it ever since.

During the boot camp, I was encouraged to read "The Little Schemer" during my free time. This book proved to be invaluable in helping me understand the concept of recursion, which has enabled me to make significant progress in my programming studies. I am now confidently working through core programming concepts and am approaching the end part of Programming Languages A.

I highly recommend "The Little Schemer" to anyone struggling with the concept of recursion. It has been a game-changer for me and I believe it can be for others too.

Thanks everyone for the comments. I'm moving on from OSSU, best of luck to all.

ossu / computer-science