Deck 9: Fractals: the Geometry of Nature: Recursion, Grammars and Production Rules

Question 1

What is the best description of the following function? 1. def hello ():
2) print("Hello World")
3) hello ()

A) It is a simple and correctly implemented recursive function.
B) It is an erroneous illustration of a recursive function.
C) It is a recursive function that will only execute once.
D) It is a recursive function that will execute exactly 10 times.

Answer 1

B

Question 2

In a recursive function, the ____ identifies when to stop.

A) recursive square
B) erroneous step
C) recursive step
D) base case

Answer 2

D

Question 3

Case Study 1:
1. def drawSquare(aTurtle, side):
2. for i in range(4):
3. aTurtle.forward(side)
4. aTurtle.right(90)
5.
6. def nestedBox(aTurtle, side):
7. if side >= 1:
8. drawSquare(aTurtle, side)
9. nestedBox(aTurtle, side - 5)
-Refer to the session in the accompanying Case Study 1. Line ____ represents the recursive step.

A) 2
B) 7
C) 8
D) 9

Answer 3

D

Question 4

Case Study 1:
1. def drawSquare(aTurtle, side):
2. for i in range(4):
3. aTurtle.forward(side)
4. aTurtle.right(90)
5.
6. def nestedBox(aTurtle, side):
7. if side >= 1:
8. drawSquare(aTurtle, side)
9. nestedBox(aTurtle, side - 5)
-Refer to the session in the accompanying Case Study 1. What happens when side is equal to zero?

A) A square of side length zero is drawn.
B) nestedBox returns without doing anything.
C) drawSquare is executed.
D) An infinite recursion occurs.

Question 5

When drawing a tree with a recursive function, what is the base case?

A) The trunk is less than some predefined number.
B) The number of branches is 20.
C) The condition becomes true.
D) The Python interpreter crashes.

Question 6

How many recursive steps are used to draw a tree?

A) Zero
B) One
C) Two
D) Three

Question 7

Case Study 2:
def sierpinski(myTurtle, p1, p2, p3, depth):
if depth > 0:
sierpinski(myTurtle, p1,
midPoint(p1, p2), midPoint(p1, p3), depth - 1)
sierpinski(myTurtle, p2,
midPoint(p2, p3), midPoint(p2, p1), depth - 1)
sierpinski(myTurtle, p3,
midPoint(p3, p1), midPoint(p3, p2), depth - 1) else:
drawTriangle(myTurtle, p1, p2, p3)
-Refer to the session in the accompanying Case Study 2. Which parameter to the sierpinski function is reduced during the recursive step?

A) p1
B) p2
C) p3
D) depth

Question 8

Case Study 2:
def sierpinski(myTurtle, p1, p2, p3, depth):
if depth > 0:
sierpinski(myTurtle, p1,
midPoint(p1, p2), midPoint(p1, p3), depth - 1)
sierpinski(myTurtle, p2,
midPoint(p2, p3), midPoint(p2, p1), depth - 1)
sierpinski(myTurtle, p3,
midPoint(p3, p1), midPoint(p3, p2), depth - 1) else:
drawTriangle(myTurtle, p1, p2, p3)
-Refer to the session in the accompanying Case Study 2. Which of the following lines correctly implements the midPoint function: def midPoint(p1, p2)?

A) return ((p1[0] + p2[0])/2.0, (p1[1] + p2[1])/2.0)
B) return ((p1[1] + p2[1])/2.0, (p1[1] + p2[1])/2.0)
C) return ((p1[0] + p2[0])/3.0, (p1[1] + p2[1])/3.0)
D) return ((p1 + p2[0])/2.0, (p1 + p2[1])/2.0)

Question 9

How is the Sierpinski triangle drawn?

A) The largest triangle is completely drawn first.
B) Half of the largest triangle is drawn first, and the other half is drawn at the end.
C) All of the smallest triangles are drawn before any part of the larger ones.
D) The larger triangle is drawn in thirds.

Question 10

When drawing a Koch snowflake, what is the simplest possible curve?

A) A straight line
B) A circle
C) A triangle
D) A square

Question 11

In computer science, a grammar consists of:

A) L-systems and Koch curves.
B) symbols and production rules.
C) base cases and recursive steps.
D) symbols and operations.

Question 12

In a grammar, the ____ is the starting point.

A) base case
B) symbol
C) axiom
D) curve

Question 13

Case Study 3:
Axiom A
Rules A → B
B → AB
-Refer to the grammar in the accompanying Case Study 3. Assuming you have AB, what is the next value in the sequence?

A) A
B) B
C) ABB
D) BAB

Question 14

Case Study 3:
Axiom A
Rules A → B
B → AB
-Refer to the grammar in the accompanying Case Study 3. When translating these rules to Python, what is the best structure to use?

A) Dictionary
B) List
C) Range
D) Namespace

Question 15

What do the characters "[" and "]" represent in the L-systems grammar?

A) Perform the operations between the surrounding elements first.
B) Save and restore the state.
C) Exit the program.
D) Invoke recursion.

Question 16

A fractal is similar to itself at a smaller and smaller scale.

Question 17

Every recursive program must have a base case in order to know when to stop.

Question 18

Recursion can be used to express mathematical functions in an elegant way.

Question 19

Writing a program to draw the Sierpinski triangle is more complex than the fractal tree, although it is still surprisingly simple.

Question 20

A fractal tree requires only one recursive call.

Question 21

Match each definition with its phrase.
-The starting point for a grammar.

A) Axiom
B) Production rule
C) L-system
D) Koch curve

Question 22

Match each definition with its phrase.
-A construct that explains how to replace a symbol in a grammar with another symbol.

A) Axiom
B) Production rule
C) L-system
D) Koch curve

Question 23

Match each definition with its phrase.
-Formal mathematical theory designed to model the growth of biological systems.

A) Axiom
B) Production rule
C) L-system
D) Koch curve

Question 24

Match each definition with its phrase.
-Fractal algorithm developed in 1904 used to draw snowflakes.

A) Axiom
B) Production rule
C) L-system
D) Koch curve

Question 25

Describe the two-step process that one should use to design well-formed recursive functions.

Question 26

Describe the purpose of the recursive step in a recursive function.

Question 27

Case Study 1:
1. def drawSquare(aTurtle, side):
2. for i in range(4):
3. aTurtle.forward(side)
4. aTurtle.right(90)
5.
6. def nestedBox(aTurtle, side):
7. if side >= 1:
8. drawSquare(aTurtle, side)
9. nestedBox(aTurtle, side - 5)
-Refer to the session in the accompanying Case Study 1. Describe how the nestedBox function works.

Question 28

Case Study 4:
1. Draw a trunk that is n units long.
2. Turn to the right 30 degrees and draw another tree with a trunk that is n − 15 units long.
3. Turn to the left 60 degrees and draw another tree with a trunk that is n − 15 units long.
-Refer to the instructions in the accompanying Case Study 4. How would you identify the base case?

Question 29

Case Study 4:
1. Draw a trunk that is n units long.
2. Turn to the right 30 degrees and draw another tree with a trunk that is n − 15 units long.
3. Turn to the left 60 degrees and draw another tree with a trunk that is n − 15 units long.
-Refer to the instructions in the accompanying Case Study 4. Describe the recursive step(s).

Question 30

Describe the Sierpinski triangle.

Question 31

Describe how you could implement a recursive function to draw a Sierpinski triangle.

Question 32

In computer science terms, what is a grammar?

Question 33

Case Study 3:
Axiom A
Rules A → B
B → AB
-Refer to the production rules in the accompanying Case Study 3. How would you represent these rules in Python?