A robot on a Cartesian grid can perform three moves: $F$ moves forward, $R$ turns right 90 degrees, $L$ turns left 90 degrees. The robot can be programmed and all its programs are recursive, apart from a few base cases. For example, a program could be $P_{n+1}=RP_nLQ_0R$ with $P_0=F,Q_0=F.$
Design a recursive program $P_n$ which makes the robot trace an equidistant square spiral as it moves on the grid. By “equidistant” we mean that the distance between any two closest parallel arms of the spiral is constant (but not necessarily equal to 1).
-
- Give a recursive definition for
$a_n = 1 + 2 + \cdots + n.$ - Design a recursive program
$X_n$that draws an$n$-step staircase pattern.
- Give a recursive definition for
-
Try drawing a square spiral using the three moves
$F,$$L$and$R.$Write down the sequence of moves you use. -
Find a pattern in the sequence obtained.
-
… by paying attention to the length of each straight segment of the spiral.
-
How about breaking the problem down into smaller tasks?
-
… one of which is drawing the arm of the spiral.
-
Find a recursive expression for
$Q_n=FFF\ldots$(repeated$n$times) - the program to draw one straight segment of the spiral. -
Have you tried using
$Q_n$in your expression for$P_n$- the program to draw the square spiral? -
… by considering how to draw the
$n$-stage square spiral from the$(n-1)$-stage one.
-
Drawing the spiral can lead to the natural choice of
$$FRFRFFRFFRFFFRFFFR...$$At each stage, we draw 2 perpendicular lines, whose length increases each time - hence we add one
$F$at each stage. The tricky part is the increasing length, so let’s just focus on that and come up with an expression for$Q_n=FFF\ldots$(repeated$n$times). The base case is simply$Q_1 = F.$For the recursive case, we just need to add on a single$F,$which gives$Q_{n+1}=FQ_n.$Now we can tackle
$P_n.$Let’s say$n$refers to the stage we’re at: the length of the segments we are drawing is$n,$so$P_1=FRFR.$Now to get$P_n,$we have to draw the spiral up to stage$n-1,$which is$P_{n-1},$and then we add the two arms of length$n,$for which we can just use$Q_n$from above. Putting this together, we get$P_n=P_{n-1}Q_nRQ_nR.$Note: There are multiple correct answers to this - we presented only one here.