Page 2: Pascal’s Triangle and Efficiency

Unit 8, Lab 5, Page 2

Here’s one solution to the pascal block:
pascal(row)(column){if(column=0 or column=row){report(1)} else{report(pascal(row-1)(column-1) + pascal(row-1)(column))}}

There are two base cases, the beginning and end of a row. The recursive case calculates the sum of two values in the previous row.

pascal(14)(5) = pascal(13)(4) + pascal(13)(5)

You are about to figure out how many recursive calls are needed to compute a value in Pascal’s Triangle.

What could you insert inside the block to track this?

  1. Modify your pascal block to keep count of how many times the block is executed.

  1. How many times is the pascal block called when calculating pascal(14)(5) ?

  1. What happens when you call pascal(20)(5) ?

Many of the recursive calls are redundant. For example, pascal(14)(5) will call pascal(10)(3) many times, asking for the same information.

Track what pascal(14)(5) actually calls to see the redundancy.

Take It Further…

This technique is called memoization. This is not a typo; there’s no “r” in the word. Each recorded answer is like a “memo”.

  1. Use a list structure to keep track of already-computed values of pascal, so that when the same inputs are given again, the function looks up the saved value instead of making more recursive calls.

  1. There is a direct formula for pascal that is often used:

    Build a version of pascal that uses the formula. Compare the efficiency of this version to the recursive version, and determine whether each version runs in constant time, linear time, quadratic time, or exponential time.