# Practice Paper 4 Question 9

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).

## Related topics

## Warm-up Questions

- Give a recursive definition for \(a_n = 1 + 2 + \cdots + n.\)
- Design a recursive program \(X_n\) that draws an \(n\)-step staircase pattern.

## Hints

- Hint 1Try drawing a square spiral using the three moves \(F,\) \(L\) and \(R.\) Write down the sequence of moves you use.
- Hint 2Find a pattern in the sequence obtained.
- Hint 3... by paying attention to the length of each straight segment of the spiral.
- Hint 4How about breaking the problem down into smaller tasks?
- Hint 5... one of which is drawing the arm of the spiral.
- Hint 6Find a recursive expression for \(Q_n=FFF\ldots\) (repeated \(n\) times) - the program to draw one straight segment of the spiral.
- Hint 7Have you tried using \(Q_n\) in your expression for \(P_n\) - the program to draw the square spiral?
- Hint 8... by considering how to draw the \(n\)-stage square spiral from the \((n-1)\)-stage one.

## Solution

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.

If you have queries or suggestions about the content on this page or the CSAT Practice Platform then you can write to us at oi.[email protected]. Please do not write to this address regarding general admissions or course queries.