Lab 01 for CS112: Recursion and Order Notation

Teaching Fellow: Diane H. Theriault (,

Main course web page:

Lab page url:
Lab times: Monday: 10-11, 11-12. Friday 2-3

Topics: Recursion, Efficient Exponentiation, Tidbits for homework 1.

Class Notes

Skeleton Code:,

Solution Code:,


  • Recursion is defining the solution to a big problem in terms of a similar, but slightly smaller problem.
  • Recursive solutions have a base case and a recursive invocation
  • Stack frames let each invocation of a function have its own private copy of all of its variables. This is the same for recursive functions as it is for "normal" functions
  • Use wishful thinking to understand recursive problems. Keep track of the variables that are changing vs. the variables that are constant.
  • Practical Lab: implement a recursive solution to exponentiation. Count the number of calls made to your function with and without various optimizations