D.4 Advanced Program Development

Recursion

Recursion

• A method where the solution to a problem depends on the solutions to smaller instances of the same problem. It calls itself.

Applications of Recursion

• Not really used in practice. They are difficult for humans to follow in order to understand and maintain code

• Only used when they can provide an elegant solution

  • Fibonacci given a number

  • Factorial or power of a given number

  • Print a binary tree

  • Reverse a string

Object Refrence

• A reference to an object in memory

• Used in java by the dot notation to access the fields and methods

  • Person p = new Person();

  • p.setName(“Fred”)

• p = object reference

Features of the ADT List

• A list is a data structure that can grow in size at runtime as memory is allocated dynamically

• A list is a generic ADT (abstract data type) and usually has a few basic methods

• They can be indexed to allow the program to add and remove elements from specified positions

Generic ADT Methods

• Add

• Size

• Get

• isEmpty

• Remove

Stacks

• First element added to the stack sits on the bottom

• Last one added is the first one removed

• LIFO

• The add method is a push and the remove a pop

Queues

• Elements are added to the end of the queue and removed from the front

• FIFO

• Add method is an enqueue and remove is dequeue

Methods and Algorithms for Manipulating Lists and Object References

• add (to front and back)

• insert (in order)

• delete

• list (print)

• isEmpty

• isFull

When are stacks used in operating systems?

• To keep track of instructions and which to execute next

  • Hence stackOverFlow error

• Also used to keep track of events in the software so the undo button can be used

Binary trees

• Ordered list of elements where elements of a lower number or letter are stored to the left of the node and elements of a higher number or letter are stored to the right of the node

• Have a root at the top - search start point

• Recursion used to print them

• Can traverse in pre-order, post-order, and in-order

Code Naming Conventions

• Start class names with a capital letter

• Objects with a lowercase letter

• Use meaningful names for the fields and variables

• Indent the code

• Inline annotaitons

Why are naming conventions important?

• Code is read more often than written

  • If all code is written the same it is easy to read

• Cuts down time on maintenance and reduces the chance of error through misinterpretation

• Saves time, money, and effort

• Makes it easy to read and update