Recursion: Not that hard

In July, I taught Java to about 30 high school students who had little or no prior programming experience. The curriculum was largely set for me, so I won't comment on the choice of language or lots of other things that I might be opinionated about.

In the course of teaching the students about methods, fairly early in their experience, I gave them the challenge of figuring out how to right a program that would print out the first several numbers in the fibonacci sequence. First we worked through the algorithm of how to find out a given fibonacci number: I wrote up a sequence and challenged them to figure out the formula:

n	fib(n)
0	0
1	1
2	1
3	2
4	3
5	5
n	???

After a few false starts, they figured out that fib(n) = fib(n-1) + fib(n-2) except for fib(0) = 0 and fib(1) = 1. 

Now, to be completely honest, I had forgotten that there's an iterative way to solve fibonacci, because the recursive way is SO OBVIOUS. 

So I told them that another thing about methods, in addition to them being able to take parameters and return values, is that they can call themselves. And thus, they wrote recursive algorithms, without pain or suffering:

if (n=0) {return 0;}

else if (n=1) {return 1;}

else {return (fib(n-1) + fib(n-2));}

And some undergraduates who observed it expressed great concern because recursion is a topic they cover in data structures and therefore obviously complex and advanced and presumably inappropriate for my poor little inexperienced high schoolers. Who, I must say, did not appear confused or scarred in any way from the experience.

Clearly there's lots more about recursion I didn't cover, not the least of which is why this is a pretty inefficient solution. But this experience - where recursion was the obvious solution to a problem and there was a straightforward way to handle it - seemed like a nice little introduction to the idea that a method can call itself. No need for awe and fear. And I wonder, if we just introduced recursion as the obvious solution to a few easy problems and handled the more complicated pieces later when students are more prepared, would it go better? 

I think next time, after I gave the students a day or two to adjust to writing methods, control structures, parameters and return values, I'd return to the idea of efficiency and why some solutions are more efficient than others in different ways. 

Interview

There's an interview with Laura Blankenship that I've been ruminating on. Laura teaches computer science to middle schoolers at an all-girls school and blogs at Geeky Mom.

I like her blog a lot, so it doesn't seem like I have a problem with Laura. I do seem to have a problem with the interview, which I haven't quite pinned down.

Part of it is probably the quote, "8th graders hate everything." That hasn't been my experience at all! Middle schoolers like to whine, but they're also frequently engaged and excited and passionate. I think Laura would agree, so it feels like picking nits, but at the same time, the quote really bothers me, maybe because it's at the very beginning of the interview, so it sets the tone.

There's something else about it too. Maybe the generalizations about what kids can and can't do. I find huge variation between students. But I'm not really sure why I keep coming back to it. Maybe because it's so short and poses a lot of questions without a lot of context or solutions.

I'm usually not surprised when students can't do or don't know about something complex that they've never been taught or never been asked to think about before. Have you ever thought about the electricity that powers the devices in your house? Or do you just plug things in and expect them to work? I think the web is like that for kids - unless we point out that there's a huge infrastructure behind things and that the devices (websites) they use can be deconstructed and that they could make their own things, why would they think about it? The web is just there, it's always been there, like electricity or (for those who are young enough) TV. Like electricity, we need to decide what is important enough for students to learn.

The Age of Cassandra

Kristen Marhaver is a PhD student studying coral biology who wrote the absolutely fascinating Ecosystems in the Age of Cassandra in the May 5 Science Progress. She cites Adam Cohen's New York Times editorial wondering why policymakers do not react appropriately to scientific warnings of impending disaster such as the Hurricane Katrina flooding, September 11th attacks, and Bernie Madoff fraudulence.

Marhaver suggests that the problem is the difference in pace between science, which takes years to research and verify, and news, which doesn't spend more than a day or two on a story, especially one about scientific research or predictions. She has a number of notable suggestions for indicating to publishers and policymakers which research is really, really important and making research findings openly available.

The comments are worth reading as well, especially for people who want to make their message heard. One journalist remarks on the importance of a story - protagonist, antagonist, beginning, middle, end. People respond to research written with a narrative theme. They respond to the stories of individuals too - "the death of one man is a tragedy, the death of millions is a statistic" (misattributed to Stalin).

There are systemic problems leading to a failure on our part to heed important warnings. Research reports written for peer-reviewed journals aren't necessarily appropriate for lay people, even when the information is crucial. And researchers who are embedded in their own little world may miss the forest of the larger world for the trees of their own point of view.

Scientists must find ways to choose the message and frame it in a way that important audiences can hear and act on. Policymakers have many competing interests. So does industry. So does the public at large, so do teachers, so do students, but they aren't all the same interests. It's important to figure out what messages are crucial and which can be heard and by whom. Then we can hope for success in making the world a better place.

Computer Science Around Programming

Alfred Thompson posted Computer Science Before Programming, where he starts by considering the new trend of courses that teach introductory CS without relying on programming-first. He quickly moves into a discussion of different levels of programming languages and focuses on the question of whether "post-syntax" languages such as Scratch, Alice, and Kodu expose the right concepts, such as how loops work.

I think that even when we focus and try hard, we all too often fall into the trap of thinking that the big ideas of programming are synonymous with the big ideas of computer science. We all learned CS through programming first, and it's our mental model of how it works. Changing such an ingrained mental model, especially when nearly everyone around you is reinforcing the model, is hard.

I believe that programming is to computer science as experimentation is to other sciences. It is the work of professionals in the field. It is how we develop new ideas. And it is a skill that must be learned before it can be used in a meaningful way.

We don't make students experimentally derive all we know about science from first principles - we tell them the formula for acceleration, the value of the force of gravity, the periodic table of elements. We don't make them figure these things out, and it's a good thing because usually they don't have the skill or tools to accurately measure these known quantities.

Now, some people will be saying, "but we TELL them about conditionals and loops and parameters and abstract classes!" Those are big ideas of programming. Not of computer science.

Here are some of the big ideas of computer science:

• The design of things is impacted by the assumptions and experience of the people who make them.
• The computational devices we use affect our society. And related: there are ethical implications to computational tools.
• What is computing good for and what is it bad for?
• How do we abstract details to model problems and find solutions?
• What does it mean that computers run on binary when we have beautiful user interfaces?

I can teach every one of those, and lots of others, with no formal programming languages. Programming would only get in the way of what could be a rich discussion and deep understanding.

Students should experience programming - it's empowering and fun and an important part of computer science. But we shouldn't confuse the skill of programming with the concepts of computer science.

Ada Lovelace Day

I think people who work at the intersection of computer science and other disciplines do some of the most interesting work there is. In particular, I think there are women doing amazing work at the intersection of the social sciences (like linguistics and sociology) and computer science.

Jane Margolis is my hero because she has looked critically at the culture of computer science and not only found ways in which it is unwelcoming to some groups (notably girls and minorities) but has also worked passionately to change it. In particular, her work with the Computer Science Equity Alliance is inspirational. Jane is energetic and thoughtful and perceptive, and she constantly works to make the world of computer science better.

Jane introduced me to another of my heroes, Justine Cassell. I first learned of her because of the book From Barbie to Mortal Kombat. I had the opportunity to talk to her briefly at the Hopper conference this fall and was so impressed by her analytical mind and energetic presentation. Justine has also done a lot of interesting work on gender and technology.

Finally, the researchers of ABI and NCWIT earn my respect every time I talk to them. Catherine Ashcraft had the most interesting observations about gendered behavior and how it is different from sex, which convinced me she's brilliant. Lecia Barker and Caroline Simard produce consistently fascinating research.

This post was produced for my Ada Lovelace pledge. Two other posts on this subject I found inspiring today were "Why Care about Gender?" and "The Impact of Positive Female Role Models"

Mental math

I believe in growth mindset - the idea that you can get better at things by working at them. It can be a hard thing to live at times - we all seem to have certain places where we have blinders about our ability to improve (or our students' ability to improve!)

With that in mind, I have been working on my mental math abilities. I've been playing a game where I keep track of changing numbers by adding and subtracting. The numbers are pretty small - usually less than 10, though not always, but the running total can grow fairly large.

I am sure that it's good for my brain to play this game, that I'm improving my ability to do mental math.

Here's what I wonder, though: does it matter if I get the right answer? I have discovered at times that as I keep track of the running total, I have made computational errors - not particularly surprising, since it isn't something I'm particularly stellar at. My sense is that it's the activity of trying the math rather than getting the right answer that's important, especially since I doubt that I'm reinforcing bad math by occasionally adding numbers incorrectly. However, I can believe it would be a problem to form neural pathways to bad computation. I don't know of any studies that have looked at this, so I'm not sure we know the answer.

Encountering the Other

I've been thinking a lot about constructivism and constructionism and Freire and diversity lately. I can believe that almost totally open-ended discussions and activities can be engaging and educational. (Almost totally open-ended! Not totally open-ended! Though there's a good point in A Mathematician's Lament that anything one doesn't stumble across in 12 years of thinking about a topic probably isn't all that important.)

I am thinking of knowing the kind of activity you want kids to engage in, but allowing them to propose all the particulars. Let them figure out what the important parts are. Say you want them to learn how to write a program. Ask them what kind of program they want to write. What kind of problems do they have that could be solved with a program? Then let them figure out (with support) how to write the program - they figure out the constructs, you provide the syntax. It's just-in-time teaching. At an extreme, you might even be able to let them figure out what they wanted to learn at all in the context of your class, but without them knowing something about the context it seems like proposing problems is a better way to start.

I have a hard time believing this way of teaching is scalable - how can you get all the thousands of teachers in this country to be that open-ended? It's hard and you have to have an incredible grasp of the material to be able to guide students gently. (Or perhaps you could pull it off if you knew nothing, with teacher and class learning it together, but that's not comfortable for most teachers!) That said, as I have practiced open-ended teaching more and more, I've become better at it, which makes me think it is teachable, which means it might be scalable. It would require a sea change in how we think about education - we might not get to all the standards this way.

The extreme educational theorists believe in this way of teaching because of its respect for students' culture and experience. And I haven't ever questioned that, except to contemplate that the historical role of education in the US is to inculturate children into the dominant value set and that if we take underprivileged students and fail to give them that clue, we do them a disservice when they have to compete as adults in the dominant culture. (I am a terrible teacher because I will regularly point out to underprivileged students how to fly under the radar like the privileged kids do.)

So it was with great interest that I read Siobhan Curious' latest post: Encountering the Other about the role of literature in our lives. Specifically, she has a quote from a Harper's article Dehumanized: When Math and Science Rule the School:

Happily ignoring the fact that the whole point of reading is to force us into an encounter with the other, our high schools and colleges labor mightily to provide students with mirrors of their own experience, lest they be made uncomfortable, effectively undercutting diversity in the name of diversity.

One is wise enough to think one should tread lightly on a discussion of valuing diversity vs. valuing the dominant culture (as though one can't value both!) So one will stop writing now other than to wonder what you think?