CIS 3020 Part 4 - Revision history

Jka: /* Linear Recursion */

2007-03-23T18:54:25Z

Linear Recursion

Jka: /* Bound Variables */

2007-03-23T18:12:49Z

Bound Variables

Jka at 17:37, 23 March 2007

2007-03-23T17:37:57Z

New page

==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===
{| border="1"
! 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:
{| border="1"
|
<pre>
public int test (int x) {
body1
}
</pre>
||
<pre>
public int square (int x) {
body2
}
</pre>
|}
are the two '''x''''s the same?

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

← Older revision		Revision as of 18:54, 23 March 2007
Line 76:		Line 76:
	n! = n * (n-1)!		n! = n * (n-1)!
	</pre>		</pre>
		+	===Analysis for factorial===
		+	* Inputs: n
		+	* Outputs: n!
		+	* Constraints: n>0, integer
		+	* Assumptions: None
		+	* Relationships: None
		+	===Design for factorial===
		+	# If n<=1 then
		+	## Result = 1
		+	# If n is any other value then
		+	## Result is n * (n-1)! or n * fac(n-1)
		+	===Implementation===
		+	<pre>
		+	public int fac(int n) {
		+	int result;
		+	if (n==1) {
		+	result = 1;
		+	} else {
		+	result = n * fac(n-1);
		+	}
		+	return result;
		+	}
		+	</pre>
		+	===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 <code>n * fac(n-1)</code> do the computation ''in the other direction'':
		+	<pre>
		+	1 * 2 * 3 * ... * (n-1) * n
		+	</pre>
		+	===Analysis for alternative factorial===
		+	* Inputs: n
		+	* Outputs: n!
		+	* Constraints: n>0, integer
		+	* Assumptions: None
		+	* Relationships: None
		+	<center>Note that this is identical to the first analysis</center>
		+	* 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===
		+	# If counter > n then
		+	## Result is product we have been computing
		+	# If counter is any other value then
		+	## Product is our product so far * the counter
		+	## Increment the counter
		+	## Try again
		+	# What must our counter start at?
		+	## 1
		+	# What must our product start at?
		+	## 1
		+	===Implementation===
		+	<pre>
		+	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;
		+	}
		+	</pre>
		+	===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
		+	==Continue with [[CIS 3020 Part 5]]==

← Older revision		Revision as of 18:12, 23 March 2007
Line 43:		Line 43:

	No! These are formal parameters of their respective methods. The method definitions bind them.		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
		+	<pre>
		+	public boolean goodEnough(double guess, double x) {
		+	return (abs(square(guess) -x) < 0.001);
		+	}
		+	</pre>
		+	* 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:
		+	<pre>
		+	n! = n * (n-1) * (n-2) * ... * 3 * 2 * 1
		+	</pre>
		+	* Note that this is the same as:
		+	<pre>
		+	n * (n-1) * (n-2) * ... * 3 * 2 * 1 = n * (n-1)!
		+	</pre>
		+	i.e.
		+	<pre>
		+	n! = n * (n-1)!
		+	</pre>