Computer Science- Recursion, Iteration, and Lists (Test 2) Flashcards
(20 cards)
1
Q
stepper
A
helps identify your mistakes
2
Q
trace diagram
A
- traces steps of function
- start with the function call
3
Q
recursive
A
- uses itself to define itself
- one that calls itself
4
Q
base case (exit case)
A
- simple case value we know how to evaluate without a recursive call
- stops the recursion
5
Q
recursive reduction
A
- function calls a simpler version of itself/ version closer to “the answer”
- must eventually read the base case
6
Q
Developing A Recursive Procedure
A
- write down simple cases and expect answers
- write a case that is slightly more complex than base case
- how can i get this case to above case and what must be done to the reduction?
7
Q
To Approximate the Square Root of n
A
- make a guess
- divide n by the guess
- add the result to your guess
- take half of the sum
8
Q
E(psilon)
A
identifies acceptable region
9
Q
stack memory
A
- each slot is removed, one by one, from top to bottom
- bottom is the function being evaluated and the top is the base case
- THE BOTTOM IS THE DEFERRED (DELAYED) OPERATION
10
Q
Hallmarks of Iteration
A
- no deferred/delayed operation
- a fixed # of state variables whose values precisely specify the current state
- fixed transition rule
- an (optional) end test: specify conditions under which the process should terminate
11
Q
fixed transition rule (iteration)
A
describes how the state variables are updated as the process moves from state to state
12
Q
Writing Recursive Procedures That Will Generate An Iterative Process
A
- generally needs a helper function
- generally helper fxn needs 1 more input than wrapper
- devise transition rule, then translate to scheme
13
Q
proof
A
an irrefutable argument
14
Q
LISP
A
- list processing
- scheme is a dialect of LISP
15
Q
2 rules of scheme
A
- everything is a list
- everything is a function
16
Q
List in Scheme
A
- is comprised of the empty list and 0 or more elements
- a single quote tells scheme: “do not try to interpret what follows as a function”
- comprised of 2 parts: CAR and CDR
17
Q
CAR
A
- first element of list
- outputs can be either: LIST, ATOM, OR ERROR
18
Q
CDR
A
- everything expect first element
- outputs can be either: LIST OR ERROR (cdr ‘( ))
19
Q
Cons Cell Diagram
A
- left compartment: car part of each block, can hold ATOM AND ORIGIN OF ARROW
- right compartment: cdr part, can hold ORIGIN OF ARROW
20
Q
Writing List-Processing Functions
A
- (null? L) is usually the base case
- a list decomposes into CAR & CDR
- examine CAR to determine possible case THEN accordigly, make recursive call on CDR
