Deck 7: Recursive Algorithms

Question 1

Ferns have a recursive structure.

Answer 1

True

Question 2

The following short story is considered to be recursive:
Once upon a time a young princess was sitting with her father, the king. She said to her father, "My Royal Father, can you read me a story?"
Yes, my Royal Daughter," said the king, as he opened the Royal Storybook. He began to read, "Once upon a time a young princess was sitting with her father, the king. She said to her father, 'My Royal Father, can you read me a story?'"
"Yes, my Royal Daughter," said the king, as he opened the Royal Storybook. He began to read, "Once upon a time a young princess was sitting with her father, the king. She said to her father, 'My Royal Father, can you read me a story?' . . ."

Answer 2

True

Question 3

The marble floor of the Sistine Chapel has patterns in the tiles that is an example of a mathematical design called a Sierpinski gasket.

Answer 3

True

Question 4

The Sierpinski gasket algorithm splits the triangle into four smaller triangles, and then calls itself for three of the four smaller triangles.

Question 5

The power of recursion in computer programming is the way in which computer scientists use recursive algorithms to analyze and solve complex problems.

Question 6

An object is really just a set of instructions describing how to complete a process.

Question 7

Recursion can describe a very sophisticated process with a simple and efficient set of instructions.

Question 8

There is some evidence that the human brain is recursive.

Question 9

Blood vessels in the human body have a structure that can be best described by recursion.

Question 10

The pattern of seeds on the head of a sunflower, the geometry of a snail's shell, and even DNA gene sequencing all appear to be recursive structures.

Question 11

Seemingly random events, such as an electronic interference in a telephone circuit, can be described using recursive functions.

Question 12

An understanding of recursion is essential to programming any algorithm.

Question 13

Many of the most important algorithms in computing - such as those used to search large databases quickly - depend on the use of recursion.

Question 14

Often it is better to use recursion instead of iteration for methods that can be written using a simple loop.

Question 15

The computer must set up a section in its memory every time a new method is called - except when the new method is a copy of an existing method.

Question 16

A method that uses linear recursion can very quickly generate many copies of itself to work simultaneously on smaller examples of the overall problem.

Question 17

Generally, a method that uses exponential recursion is often very easy to replace with a more efficient iterative solution.

Question 18

Exponentially recursive algorithms are often far more efficient than iterative solutions because they can repeatedly break a problem into several smaller parts and then attack those smaller parts in a way that an iterative algorithm cannot.

Question 19

Even after taking into account the overhead, iterative algorithms are usually far more efficient than recursive solutions.

Question 20

For simple tasks that can be described with linear recursion, iteration seems to be a better choice.

Question 21

For complex problems that can be broken down into smaller parts, linear recursion usually works much better.

Question 22

On a computer, conditional recursion continues until all available memory is used, or until it triggers some time-out mechanism in the operating system.

Question 23

A properly structured recursive algorithm should always contain a Boolean expression in a selection sequence.

Question 24

In conditional exponentially recursive algorithms, the recursive step breaks the problem into smaller parts, and then calls the algorithm itself for each of those parts, continuing to do so until the base case is reached.

Question 25

After reading the specifications for a project, a good programmer should put together a set of questions for the person who provided the specifications.

Question 26

In computer programming, an algorithm that calls itself is said to be ____.

A) iterative
B) recursive
C) cyclic
D) repetitive

Question 27

A(n) ____ is one that uses a loop to repeat a set of instructions.

A) cyclic process
B) iterative process
C) repetitive process
D) recursive process

Question 28

The term ____ is just another name for looping.

A) iteration
B) recursion
C) encapsulation
D) orientation

Question 29

The term ____ is used to describe the processor time and storage space in a computer's memory needed to manage a method as it runs.

A) outlay
B) cost
C) price
D) overhead

Question 30

____ occurs when a method calls itself only once each time through the method.

A) Linear recursion
B) Infinite recursion
C) Exponential recursion
D) Mutual recursion

Question 31

The recursive Sierpinski gasket algorithm is an example of ____ because it calls itself three times.

A) linear recursion
B) mutual recursion
C) exponential recursion
D) iteration

Question 32

A linear recursion graph looks like a ____.

A) parabola
B) straight line
C) ellipse
D) circle

Question 33

An exponential recursion graph looks like a ____.

A) polygon
B) straight line
C) circle
D) curve

Question 34

At each level of exponential recursion, the number of copies of the program ____.

A) doubles
B) triples
C) quadruples
D) quintuples

Question 35

The following algorithm is an example of ____.
Begin with an equilateral triangle
Sierpinski (triangle)
Start
Find the midpoint of each side of the triangle
Draw lines connecting the midpoints, which will form four smaller triangles that can be called triangles A, B, C, and D, with D in the center and the others around it.
Color in (or cut out) the center triangle // triangle D
Do Sierpinski (triangle A)
Do Sierpinski (triangle B)
Do Sierpinski (triangle C)
Stop

A) linear recursion
B) iteration
C) mutual recursion
D) infinite recursion

Question 36

____ occurs when a method calls itself more than once in each pass through a method.

A) Linear recursion
B) Iteration
C) Exponential recursion
D) Tail recursion

Question 37

The term ____ implies that an algorithm calls itself repeatedly without stopping.

A) tail recursion
B) iteration
C) linear recursion
D) infinite recursion

Question 38

____ occurs when an algorithm does not contain any instructions about when to stop the recursion.

A) Tail recursion
B) Iteration
C) Binary recursion
D) Infinite recursion

Question 39

Recursion that is not infinite is called ____.

A) mutual recursion
B) conditional recursion
C) binary recursion
D) iteration

Question 40

The condition that stops the recursion is called the ____.

A) end condition
B) stop order
C) end case
D) base condition

Question 41

A recursive algorithm usually contains a(n) ____ instruction that causes the algorithm to keep calling itself until the base condition is met.

A) For
B) Stop
C) IF/ELSE
D) Start

Question 42

In Alice, clicking on the ____ button allows you to enter Scene Editor mode.

A) Add instance to world
B) Done
C) Open
D) ADD OBJECTS

Question 43

In Alice, the ____ button can be used if you are unhappy with one of your moves.

A) Add instance to world
B) Undo
C) create new method
D) ADD OBJECTS

Question 44

The pseudocode for a recursive method is shown below. What statement is missing from the area labeled (a)?
Biplane.taxi (target)
(a)
If ( [biplane.distance to target] > 1 meter)
{
Biplane.point at target
Biplane.move forward 1 meter
(b)
}
(c)

A) Start
B) Do together
C) biplane.taxi (target)
D) Stop

Question 45

The pseudocode for a recursive method is shown below. What statement is missing from the area labeled (b)?
Biplane.taxi (target)
(a)
If ( [biplane.distance to target] > 1 meter)
{
Biplane.point at target
Biplane.move forward 1 meter
(b)
}
(c)

A) Start
B) Do together
C) biplane.taxi (target)
D) Stop

Question 46

The pseudocode for an iterative method is shown below. What statement is missing from the area labeled (a)?
Sailboat.sail to (target)
(a) ( not [sailboat is within 5 meters of target] )
{
Do together
{
Sailboat.turn to face target
Sailboat.move forward 2 meters
}
}
(b)

A) For
B) If
C) While
D) Stop

Question 47

The pseudocode for an iterative method is shown below. What statement is missing from the area labeled (b)?
Sailboat.sail to (target)
(a) ( not [sailboat is within 5 meters of target] )
{
Do together
{
Sailboat.turn to face target
Sailboat.move forward 2 meters
}
}
(b)

A) For
B) If
C) While
D) Stop

Question 48

The pseudocode for a recursive method is shown below. What statement is missing from the area labeled (a)?
Sailboat.sail to (target)
(a)
If ( not [sailboat is within 5 meters of target] )
{
Do together
{
Sailboat.turn to face target
Sailboat.move forward 2 meters
}
(b)
}
(c)

A) sailboat.sail to (target)
B) Start
C) Do together
D) Stop

Question 49

The pseudocode for a recursive method is shown below. What statement is missing from the area labeled (b)?
Sailboat.sail to (target)
(a)
If ( not [sailboat is within 5 meters of target] )
{
Do together
{
Sailboat.turn to face target
Sailboat.move forward 2 meters
}
(b)
}
(c)

A) sailboat.sail to (target)
B) Start
C) Do together
D) Stop

Question 50

The pseudocode for a recursive method is shown below. What statement is missing from the area labeled (c)?
Sailboat.sail to (target)
(a)
If ( not [sailboat is within 5 meters of target] )
{
Do together
{
Sailboat.turn to face target
Sailboat.move forward 2 meters
}
(b)
}
(c)

A) sailboat.sail to (target)
B) Start
C) Do together
D) Stop