Chapter 3 Flashcards
Recursion
Breaks a problem into smaller identical problems
Iteration
- A process that is repetitive
2. A single pass through a loop
Sequential Search
An algorithm that locates an item in a collection by examining items in order, one at a time, beginning with the first item.
Binary Search
An algorithm that searches a sorted collection for a particular item by repeatedly halving the collection and determining which half could contain the number.
Base Case
The known case in a recursive definition. Also called the basis or degenerate case.
Divide and conquer
A problem-solving strategy that divides a problem into smaller problems, each of which is solved separately.
Four Questions for Constructing Recursive Solutions
- How can you define the problem in terms of a smaller problem?
- How does each recursive call diminish the size of the problem?
- What instance of the problem can serve as the base case?
- As the problem size diminishes, will you reach the base case?
Recurrence Relation
A mathematical formula that generates the terms in a sequence from previous terms.
Mathematical Induction
A method for proving properties that involve non-negative integers. Starting from a base case, you show that if a property is true for an arbitrary non-negative integer k, then the property is true for the integer k + 1.
Box Trace
A systematic way to trace the actions of a recursive method.
Activation Record
A record that contains a method’s local environment at the time of and as a result of the call to the method.
Local Environment
A method’s local variables, a copy of the actual value arguments, a return address in the calling routine, and the value or the method itself.
Fibonacci Sequence
The sequence of integers 1, 1, 2, 3, 5, . . . defined by the recurrence relationship
a1 = 1, a2 = 1, an = an-1 + an-2 for n > 2
Partition
To divide a data structure such as an array into segments.
Tail Recursion
A type of recursion in which the recursive call is the last action taken.
