Recursion/Iteration

Question 1

What is iteration and recursion an example of?

Answer 1

traversal

Question 2

What is the difference between indirect and direct iterators?

Answer 2

Direct iterator traverses throw the actual data while the indirect iterator traverses through instances of the data structure

Question 3

What is the purpose of recursion?

Answer 3

To make the code simpler

Question 4

what happens after a recursive call?

Answer 4

The method clones itself: copied,
local variables
parameters
code

Question 5

What does the base case prevent?

Answer 5

Infinite recursion

Question 6

What is Iterable?

Answer 6

an interface in java.lang

Question 7

What method must be implemented when using Iterable?

Answer 7

Iterator(), which returns an iterator object for traversing through a list: Iterator = list.iterator()

Question 8

What is Iterator?

Answer 8

An interface in java.util

Question 9

What method must be implemented when using Iterator?

Answer 9

• hasNext
• next
• remove(optional)

Question 10

What are the fields for an indirect iterator class?

Answer 10

1. ) A separate list data structure

2. ) Current position index

Question 11

What are the fields for a direct iterator class?

Answer 11

1. ) The fields that a list has
   - an array
   - numItems

2.)Current position index

Question 12

Where is the reference of recursive method after a recursive call & base case detection?

Answer 12

after the recursive call, and before the condition, respectively

Question 13

Where are the clones stored?

Answer 13

In the stack in the activation records

Question 14

Once the method returns and breaks recursive chain what happens to the current method?

Answer 14

It disappears

Question 15

What is the address of a method before the return address?

Answer 15

System

Question 16

What structure can be used when two recursive calls are added/connotated?

Answer 16

A binary tree

Question 17

What two methods can be used to analyze runtime of a recursive function?

Answer 17

1. ) informal reasoning

2. )recurrence equation

Question 18

What are the components of a recurrence equation?

Answer 18

T(N) + A + C(T(N))
A:time outside of recursive call
C: # recursive calls
N: problem size

Question 19

How do you find the worst case complexity of a recurrence function?

Answer 19

finding the closed form solution to the recurrence equation

Question 20

What are the steps to fond the closed form of a R.E?

Answer 20

make a T(N) vs. N table including the base case
look for pattern in terms of just N
verify by plugging function into T(N) in recurrence equation