Chapter 22: Recursion

Question 1

What is an anonymous array?

Answer 1

We can avoid declaring a variable to reference an array by providing a list of the elements.
New Type[] {value, value, value}

Question 2

What is a private constructor method?

Answer 2

Constructors are public because we want to permit other classes to construct objects.
Occasionally we want the creation of objects to be tightly controlled by the class itself.

Question 3

What is recursion?

Answer 3

Something is defined in terms of itself

Question 4

What is a recursive algorithm?

Answer 4

Algorithm: procedure for undertaking some class.
Recursive: expressed in terms of itself

Question 5

How do we design a recursive algorithm?

Answer 5

1. Base cases- when is the problem solved easily
2. Recursive cases- an occurrence of the problem of the same kind but simpler.
3. The solution of the simpler problem helps to solve the given one

Question 6

What is a recursive method?

Answer 6

One that contains one or more method call to itself. Any route not containing a recursive call is the base case

Question 7

What are two common misunderstandings?

Answer 7

A recursive method call makes execution go back to the beginning: It starts another separate occurrence of the method
There is one copy of each method variable belonging to a method: Each call creates a new set of method variables to be used in that execution

Question 8

What makes a recursive algorithm well defined?

Answer 8

Clearly identified range of arguments for which it is meant to work
At least one base case that doesn’t make a recursive call
In all recursive cases, arguments passed to the call are nearer to the base case than those given.

Question 9

Describe the difference between recursion and iteration

Answer 9

Many recursive methods could be easily implemented by iteration. Iteration is an optimized implementation of tail recursion

Question 10

What is tail recursion?

Answer 10

There is no more work to do after the recursive call has been made

Question 11

What is multiple recursion?

Answer 11

The activation of a method can cause more than one recursive activation of the same method. Hard to express iteratively

Question 12

What is a recursive data structure?

Answer 12

A data structure that consists of objects containing a reference to other objects of the same type i.e. binary trees