Wyo C++ Ch. 18 Notes

You are only responsible for reading Sections 1 & 2 of Ch. 18. The other sections deal with topics that are taught in Wyomissing's Data Structures course and are not tested on the AP A Exam.

Objective #1: Understand recursion and use recursive functions.

• A recursive function is one that calls itself.
• Each time a recursive function calls itself, values and addresses are placed in a stack frame on the computer's stack.
• A recursive function requires an exit condition (aka base case) so that stack overflow does not occur and so that the function ends the recursive process at some point. Stack overflow occurs when all of the available memory has been used on the computer's stack. Stack overflow often crashes desktop computers.
• When you write recursive functions it is sometimes difficult to identify the proper exit condition that you need to use.
• Read Ch. 18, Section 1 on pp. 382+ closely.

Objective #2: Understand sequential searching.

• Although there are more efficient ways to search for data, a sequential search (aka linear search) is a good choice to use when the amount of data to be searched is small.
• You simply check each element of an array position by position until you find the one that you are looking for.
• In any search, the item upon which the search is based is called the key and the field being searched is called the key field.

Objective #3: Understand binary searching.

• If the data in an array is already sorted in order (alphabetically for example) then a binary search is much more efficient and quicker than a sequential search.
• In the case of a binary search, you first examine the "middle" element. If that element is "lower" (alphabetically, for example) than the element which you are looking for, then you discard the lower half of the data and continue to search the upper half. The process repeats itself when you then look at the middle element of the remaining "upper half" of the data.