9-12, Advanced Topics, AP Computer Science A

Chiming in on Recursion

I know I’m late the the recursion party (Shriram Krishnamurthi, Adam Michlin, Alfred Thompson, Mike Zamansky), but this is my first year teaching AP CSA and therefore the first time explaining recursion in technical detail so it’s been rolling around in my head a lot.  Granted, the previous posts are right that there probably isn’t a big need to teach recursion so early.  However, (a) AP requires us to, and (b) I love me some fractals.

While I don’t have the technical background of some, I don’t think we should discount the value traditional examples such as Fibonacci and factorial have from a pedagogical standpoint.  Yes, they don’t have a ton of practical applications, but they do give the students a familiar starting point since they’ve learned about these concepts in math classes.  By starting with one of these examples, you are able to break a problem down into its “simplified problem” and its “base case” using specific numbers and building up to the algorithm. Doubtful that anyone in the class will know what 8! is without a calculator, but if you tell them 7! = 5040 they’re that much closer.  Using examples like these, you can also scaffold by comparing the algorithm as a loop versus using recursion.  Plus, a great starting point if you want to talk about complexity.

What I have found to be an attention-grabbing avenue with plenty of practical applications for teaching recursion is fractals.  Though you probably don’t have the time in an AP CSA class to go in depth, the math nerd in me finds every excuse to work fractals into a lesson.  I could write a dozen posts of different fractal applications, but, for the purpose of this discussion, fractals serve as a visual representation of recursion. Another great example is to work through the process of identifying a simplified problem within Sierpinksi’s triangle (written here in Python).  Watching how it draws demonstrates the order of code execution.  Here is a fun “Snowflake” design in Java that gives a little more freedom for students to change the design, experiment with recursion, and make it their own.