Lab 01 for CS112: Recursion and Order Notation

Teaching Fellow: Diane H. Theriault (deht@cs.bu.edu, http://cs-people.bu.edu/deht)

Main course web page: http://www.cs.bu.edu/fac/byers/cs112.html

Lab page url: http://cs-people.bu.edu/deht/cs112_spring11
Lab times: Monday: 10-11, 11-12. Friday 2-3

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

Class Notes

Skeleton Code: PowerRunner.java, PowerComputer.java

Solution Code: PowerRunner.java, PowerComputer.java

Highlights

  • 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