CIS 3020 Part 4

Variables

Variable: An identifier that can be given a value

• Associated with primitive types

Reference Variable: A variable whose value is a reference

• Associated with instances of a class
• Most programmers refer to both as variables
• There is a fundamental difference in how they are used internally

String Methods

Method	Return Value	Arguments	Definition
toUpperCase	Reference to String Object	None	Shifts all alpha-characters to uppercase
toLowerCase	Reference to String Object	None	Shifts all alpha-characters to lowercase
length	int	None	Returns number of characters in string
trim	Reference to String Object	None	Removes white space from end of string object
concat	Reference to String Object	Reference to String Object	Concatenates string object in argument to original string object
substring	Reference to String Object	int	Returns substring of original string from position given to end
substring	Reference to String Object	int,int	Returns substring of original string from position given to second position given

Bound Variables

Given two methods:

public int test (int x) { body1 }

public int square (int x) { body2 }

are the two x's the same?

No! These are formal parameters of their respective methods. The method definitions bind them.

• A variable is said to be bound in an expression if the meaning of the expression is unchanged when the variable is consistently renamed throughout the expression.
• In other words, replace x with some other name like p throughout the its entire method and the definition of the method should remain the same.
• Also referred to as a "local variable".

Scope (of a name)

That portion of a program in which there is a binding for a particular name

Free name

• A variable or method name is said to be free in an expression if it is not bound

public boolean goodEnough(double guess, double x) {
  return (abs(square(guess) -x) < 0.001);
}

• Bound variables: goodEnough, guess, x
• Free variables: abs, square

Linear Recursion

• Suppose I would like to know how many students are in row 2
• Rather than counting each student, I will let them count themselves
• Each student will:
  • Give a count of 1 if no one is to their left
  • Will ask the person to their left for a count then will give an answer one larger than that value

• The factorial function is the prototype example of linear recursion:

n! = n * (n-1) * (n-2) * ... * 3 * 2 * 1

• Note that this is the same as:

n * (n-1) * (n-2) * ... * 3 * 2 * 1 = n * (n-1)!

i.e.

n! = n * (n-1)!

Analysis for factorial

• Inputs: n
• Outputs: n!
• Constraints: n>0, integer
• Assumptions: None
• Relationships: None

Design for factorial

1. If n<=1 then
   1. Result = 1
2. If n is any other value then
   1. Result is n * (n-1)! or n * fac(n-1)

Implementation

public int fac(int n) {
  int result;
  if (n==1) {
    result = 1;
  } else {
    result = n * fac(n-1);
  }
  return result;
}

Alternative Student Count

• Suppose I would like to know how many students are in row 2
• Rather than counting each student, I will let them count themselves
• Each student will:
  • Each student will tell the student to the left how many are to their right, counting themselves
  • Last person will give the total to the person on the right
  • Each student will continue to pass this value to the right

• Note that this is not the only way that we can compute factorial
• Rather than compute n * fac(n-1) do the computation in the other direction:

1 * 2 * 3 * ... * (n-1) * n

Analysis for alternative factorial

• Inputs: n
• Outputs: n!
• Constraints: n>0, integer
• Assumptions: None
• Relationships: None

Note that this is identical to the first analysis

• In this approach we keep track of the computed value (product) as we run a counter from 1 to n
• Each time we increment the counter, we multiply the product by the current value of the counter until the counter reaches n
• The counter tells us if we have reached the stopping point

Design

1. If counter > n then
   1. Result is product we have been computing
2. If counter is any other value then
   1. Product is our product so far * the counter
   2. Increment the counter
   3. Try again
3. What must our counter start at?
   1. 1
4. What must our product start at?
   1. 1

Implementation

public int fac(int n) {
  return doFac(1,1,n);
}
private int doFac(int prod, int count, int max) {
  int result;
  if (count>max) {
    result=prod;
  } else {
    result = doFac((count*prod),(count+1),max);
  }
  return result;
}

Tail Recursion

• Note that this last implementation of factorial is tail-recursive
• A tail-recursive function is one where all of the calculations are done as the recursion progresses
• As a result, the returned value is merely passed up with no further calculations