16.4 The Internal Computations


16.4 The Internal Computations

The implementations of the iterative and the recursive solutions to a problem are quite different. For the recursive solution, we must understand its implementation well to be able to develop and use it. We must understand the runtime stack, and to understand the runtime stack we must understand stack.

The stack has various applications in computer science. A stack is a data structure (a storage structure for data retention and retrieval) based on a last in first out (LIFO) discipline. The best example of a stack is a stack of plates. The last plate that was inserted is at the top of the stack and must be removed before any other can be removed.

In computer terminology, when a plate is put on the top of a stack, the operation is known as push to the stack, and the stack grows up. When a plate is taken off of the stack, the operation is known as pop off the stack, and the stack shrinks. In other words, a stack grows or shrinks depending upon the insertion or removal of plates from the stack. Figure 16.1 shows a stack of plates.

click to expand
Figure 16.1: A stack of plates.

Execution of a computer program involves two broad steps: allocating storage to hold data and then attaching a set of instructions to process the data held by the allocated storage. Some units of storage may hold data to be processed while other units may hold the results of the processing.

Generally, storage is provided for objects, constants, and methods that have local variables, constants, and parameter variables. Because recursion involves only a method, focus here is only on the associated storage of a method: local variables, constants, and parameter variables. Operating systems create a process for each program to be executed and allocate a portion of primary memory to each process. This block of memory serves as a medium for the runtime stack, which grows when a method is invoked and shrinks when the execution of a method is completed.

During the lifetime of a process, there may be many methods involved in processing; the first method is always the main method, which invokes other methods if specified by instructions. Whenever a method is invoked, the runtime system dynamically allocates storage for its local variables, constants, and parameter variables declared within the method from the allocated chunk of memory. In fact, this information is placed in a data structure known as a frame or activation record and pushed on the stack. After the execution of the invoked method is completed, the frame created for that method is popped from the stack.

Obviously, the first frame is always for the main method, as processing starts with this method. By using the analogy of a stack of plates, a frame that is created to provide storage for each method is a similar operation of a plate that is pushed on the stack and popped off the stack.

A runtime stack refers to a stack-type data structure (LIFO) associated with each process provided and maintained by the system. The runtime stack holds data of all the methods that have been invoked but not yet completed processing. A runtime stack grows and shrinks depending on the number of methods involved in processing and the interaction between them.

If the main method is the only method involved in processing, there is only one frame in the stack with storage for all the variables, locals and constants. If method main invokes another method, A, then the stack grows only by one frame. After the method A completes execution, the memory block allocated to its frame is released and returned to the system.




Object-Oriented Programming(c) From Problem Solving to Java
Object-Oriented Programming (From Problem Solving to JAVA) (Charles River Media Programming)
ISBN: 1584502878
EAN: 2147483647
Year: 2005
Pages: 184

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net