Why parallel architecture



Applications of Recursion

Factorial

Let’s write code to return n!.

What would an iterative method look like?

What would a recursive method look like?

Odd rows, write the code iteratively.

Even rows, write it recursively.

Raise your hand when done.

public int factorial(int n) {

}

public int factorial (int n) {

}

Powers

Now, modify your code to return xn.

public int poweri(int x, int n) {

}

public int powerr(int x, int n) {

}

Fibonacci sequence

In a Fibonacci sequence, each term is the sum of the two immediately preceding terms. It starts with 0 and 1:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

Base cases: fib(0) = 0, fib (1) = 1

Recursive rule: fib(n) = fib(n–1) + fib(n–2)

How can we calculate Fibonacci numbers recursively?

/** Calculate next value in Fibonacci sequence

* @param n – term to calculate, a nonnegative int

*/

public static int fib(int n) {

}

But is this a good idea? How many times is fib() called recursively when calculating …

• fib(2)?

• fib(3)?

• fib(4)?

• fib(n)?

Activation records and the call stack

High-level programming languages like Java try to “hide” the details of memory management from the programmer.

Most of the time, this is a good idea. But to understand what’s going on, especially in case of an error, it’s good to understand things like—

• where parameters are stored in memory,

• how the system gets rid of variables when they go out of scope, and

• why objects created by calls to new never go out of scope.

To learn the answers to these questions, we need to take a look at how Java allocates memory.

Memory that a Java program uses is allocated from two regions:

• The stack: This contains local variables and pointers declared in each function in the program (including the main() function).

• The heap: This contains all objects and arrays allocated by calls to new.

Let us first take a look at the stack. This is often called the run-time stack or the call stack. It behaves a lot like the stacks we learned about in Lecture 6.

• New items are pushed onto the top of the stack.

• Later, these items are popped off the top of the stack.

In the case of the run-time stack, the items that are pushed and popped are called activation records.

• Whenever a procedure is called, its activation record is pushed onto the stack.

• Whenever a procedure returns, its activation record is popped off the stack.

Suppose—

• the main program calls a function a,

• a calls a function b, and

• b calls a function c.

(See the diagram on the preceding page.)

Activation records

Let’s take a look at what’s in an activation record. For example, let’s take the activation record for function b. Suppose that function b is implemented like this:

public int b(float f, int [] ip) {

char c;

int [][] ia;

...

ia = new int[4[5];

...

return ia[0][4];

}

The activation record for b would contain the following items:

1. The return value. Space would be reserved for the int that the function is going to return.

2. The return address. This is the address of the statement that the program will return to after it finishes executing b. For example, if the code that calls b is—

...

b(3.14159, myarray);

myarray[2] = 1;

then the return address is the address of the statement myarray[2] = 1;

3. The receiver.

4. The parameters passed to the function, i.e.,

5. The local variables of the function, i.e.,

Note that are just object references. The arrays they point to are actually allocated on

We can diagram the activation record like this:

Let’s consider the five items in an activation record in more detail.

1. An activation record contains a return value unless the function’s return type is

No activation record contains more than one return value. But the return value may be an array, which is represented by an array reference.

2. Every activation record contains exactly one return address.

3. The activation record contains a reference to the receiver.

4. An activation record contains room for as many parameters as the function has. A parameter may be either—

• a simple primitive parameter passed by value. In this case, the value is passed on the stack, and it does not take up much room.

• an object reference. In this case, the address of the argument is passed on the stack, and it does not take up very much room.

5. An activation record contains room for all the local variables declared in the function. A local variable may be—

• a simple primitive variable.

• an object reference.

If a variable is a reference, then a new object or array may be created and assigned to this variable. If such an object is created, it is created on the

Recursive calls

A call stack works well with recursive calls, because it allows a separate copy of the parameters and local variables to be allocated each time a function is called.

This means that several activation records for the same function may be on the call stack at the same time.

Let’s consider the copy() method from Lecture 17:

private Node copy() {

if (next == null)

return new Node(data, null);

else return new Node(data, next.copy());

}

What would be in the activation record?

Example: Suppose that we have the list (1, 2, 3). What are the activation records created in copying it?

• The first step is to call the copy() function on the node containing 1. This creates a new node, but before it returns it, is

• The copy() function on also creates a new node, but before it returns it, calls copy() on the node containing

• The copy() function on also creates a new node.

Let’s look at the activation records created in the process.

Now, when the 3.copy() function returns, it returns a reference to the node it created. This pointer becomes the value of the second parameter of the node created by 2.copy(), so that the activation records and list copy now look like this:

After the 2.copy() returns, the link from node 1 to node is put in, and when the 1.copy() returns, it returns a copy of the list.

Although the activation records have disappeared, the nodes that they created remain.

Heap vs. stack management

On the stack, memory is allocated and freed in LIFO—last-in, first-out—fashion.

On the heap, memory is allocated whenever a is executed, and freed whenever garbage collection occurs. In most cases, it doesn’t follow a regular ordering like FIFO, LIFO, etc.

-----------------------

Stack

ia[2]

ia

c

ip

f

Return addr.

Return value

this

Storage for row 3

Storage for row 2

Storage for row 1

Storage for row 0

ia[3]

ia[0]

ia[1]

Storage for array ip

[pic]

Before call to a After call to a After call to b After call to c After c returns

Receiver.

Receiver

3

A.R. for 2.copy()

2

Return addr.

Return value

1

Return addr.

A.R. for 1.copy()

Return value

A.R.s for routines that call 1.copy()

Receiver

Receiver

Receiver

A.R. for 3.copy()

3

Return addr.

Return value

A.R. for 2.copy()

2

Return addr.

Return value

1

Return addr.

A.R. for 1.copy()

Return value

A.R.s for routines that call 1.copy()

Heap

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download