Avoiding Recursion

Table of contents:



Simpler algorithms often have smaller constant factors associated with their running-time than more sophisticated algorithms. For sufficiently small arrays, for example, insertion sort may actually be faster than Quicksort. Modify the Quicksort algorithm so that, if the region to be sorted is below a certain length, insertion sort is used instead. Using the timing techniques from Chapter 7, find an appropriate length at which to make this change.


Modify the recursive fibo() method (Figure 9-33) to simulate the call stack manually. Begin by rearranging the method so that only one step or recursive invocation occurs on each line. Define a class Frame which simulates a call frame. Finally, modify the fibo() method so that it begins by pushing a single Frame onto a fresh stack. The method then repeatedly pops the stack and handles the resulting Frame. This may result in pushing other Frames onto the stack. This loop continues until the stack is emptythat is, until there is no more work to do.

This project should leave you with a page or two of codeand a greater appreciation of recursion!

Part I: Object-Oriented Programming




Part II: Linear Structures

Stacks and Queues

Array-Based Structures

Linked Structures

Part III: Algorithms

Analysis of Algorithms

Searching and Sorting


Part IV: Trees and Sets



Part V: Advanced Topics

Advanced Linear Structures


Advanced Trees


Memory Management

Out to the Disk

Part VI: Appendices

A. Review of Java

B. Unified Modeling Language

C. Summation Formulae

D. Further Reading


Data Structures and Algorithms in Java
Data Structures and Algorithms in Java
ISBN: 0131469142
EAN: 2147483647
Year: 2004
Pages: 216
Authors: Peter Drake

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