Any suggestions on how to approach recursion and induction?

Question

Much mathematics is intimately tied to recursion, be it in definitions (like factorials and integer powers) and proofs by induction. This is also very relevant in computer science and programming. However, it is my experience that students have a hard time to understand what is going on, and even more to see where and how to apply the techniques. My impression is that by now, through decades of daily use, I'm not able anymore to see where the student's dificulties are. When presented with a problem asking for a induction proof, most are able to write down a reasonable answer, but is seems they still feel unconfortable with it. Unless specifically directed to use it, they will very rarely explore it's applicability.

Are there any suggestions on what to emphasize, what symptoms alert of particular types of misunderstandings?

Answer 1

Suppose you give a kid an input/output table such as {(0,1), (1,3), (2,7), (3,13)}, and ask your students to find a rule for this table. My experience has been that some students will try to find a closed-form rule, while others will instead notice something like a recursive pattern in the outputs. What's hard for students about recursion, I find, isn't the recursive reasoning in definitions, but instead the way of representing that in function notation. I've found it productive, in the past, to have kids informally state recursive definitions, and then validate those sloppy, informal definitions before formalizing them in accurate language and notation.

Also, I have a really great Precalculus textbook (from the CME Project) that builds a students understanding of proof by induction on top of their understanding of offering recursive definitions. It's a great textbook with a lot of fantastic ideas for teaching math, even if you're teaching more advanced material.

Answer 2

For a long time, I felt like induction was silly - because of the way most textbooks deal with it - giving inductive proofs for things that have more useful constructive proofs. Teach recursion through examples that need it. I would love to accumulate some good examples here.

I've seen better examples in programming courses (which I taught long, long ago) than in math courses. I once tried to figure the odds of winning the dice game of Craps. That is best done recursively, I believe.

Answer 3

Let's remember that there are even advanced mathematicians still trying to work out inductive proofs. its a complex topic at the heart of math/CS also. Suggest studying the Fibonacci sequence. Suggest studying the different formulas for it, constrasting the recursive one versus Binet's formula.

Suggest studying it from a CS point of view. Show computer experiments that compute recursive formulas/functions and then show "debug output" of them running. Show how an inductive proof is like a recursive program running. another great area for recursion/induction analysis is sorting e.g. quicksort and other recursive sort algorithms.

There are many ideas/exercises in the following book, one of the classics that focuses on the tight coupling between induction & recursion in CS/math: Structure & Intrepretation of computer programs Abelson/Sussman MIT which uses Scheme, a variant of Lisp (and built out of Lambda calculus).

It might help to study induction across different math fields, e.g. show an inductive proof in calculus, number theory, computer science one right after the other and show the basic "architecture" of the concept.