Unit 8 Optional Project: Pascal's Triangle Teacher Guide

Pascal's Triangle. Students build a block to compute values in Pascal's Triangle, a branched recursive function. The code closely follows the idea that each number in the triangle is the sum of two numbers above it. The project includes some discussion of the efficiency of the recursion, and some options for improving it.

Page 1: Pascal's Triangle.
- Learning Goal: Understand branched recursion and functions.
- Tips:
  - Many students will make errors about the numbers in each row, because of the different indexing involved. It is helpful to tell students that the "first" number in the nth row is n. (The "zeroth" number is 1.) Even so, expect many debugging issues to come up around improper indexing.
  - For students to write the general recursion here, it is very helpful to give multiple numeric examples like the ones used. More numeric examples are better than trying to explain the generalization directly, because that gives away the code students will write.
  - Students will make errors by ignoring the base cases, notably the 1s at the end of a given row. This base case is necessary or an indexing error may occur.
Page 2: Pascal's Triangle and Efficiency.
- Learning Goal: Understand that the running time for pascal can differ significantly depending on the algorithm used.
- Tips:
  - Students may think something is broken when calling pascal with high inputs: this is the effect of the massive recursion. Including a visible counter variable can show students that things are working. However, you'll need to watch for the difference between a long recursion, and an infinite one caused by an error in base cases.
  - Advanced students focusing on memoization may decide to scrap the recursion for iteration, and this is fine; encourage them to use recursion if they can figure out how to do so. (Don't let them think that the inefficiency is because of recursion. We could write inefficient iterative code, or efficient recursive code.) The memoization function will track the list of known values, use it when one is available, and record a new value when not available. For a simpler version of memoization, you could ask students to build an efficient calculator of Fibonacci numbers using this concept.

Optional Project: Pascal's Triangle

Pacing

Lab Pages

Solutions