• Exam ...

• Example: Personnel Database
• Employees
• Departments
• Job Descriptions

• Function invokes itself

• decomposing problem
• base case
• recursive case which gets closer to solution
• Factorial
  • n! = n * (n-1)!
  • 0! = 1

• Raw multiplications
  • X^N = X * X * X * ... * X
  • N-1 multiplications
• Save work; clump things together
  • SX = X * X
  • X^N = SX * SX * ... * SX
  • roughly N/2 times ...
• Refine this latter approach

• Base case: X^0 = 1.0
• N is even case: X^N = X^(N/2) * X^(N/2)
• N is odd case: X^N = X * X^(N/2) * X^(N/2)

Any nontrivial computer language that one can invent is apparently capable of computing no more and no fewer functions that all the other nontrivial programming languages.

This part of Java lets you solve all kinds of algorithms