The CSAT and Practice[+] are designed by the Climb Foundation to help candidates. We are advocates for more opportunity to shine and less opportunity to fail, and we strive to level the playing field.

The Computer Laboratory

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

The above links are provided as is. They are not affiliated with the Climb Foundation unless otherwise specified.

Warm-up Questions

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

Hints

  • Hint 1
    Try drawing a square spiral using the three moves \(F,\) \(L\) and \(R.\) Write down the sequence of moves you use.
  • Hint 2
    Find a pattern in the sequence obtained.
  • Hint 3
    ... by paying attention to the length of each straight segment of the spiral.
  • Hint 4
    How about breaking the problem down into smaller tasks?
  • Hint 5
    ... one of which is drawing the arm of the spiral.
  • Hint 6
    Find a recursive expression for \(Q_n=FFF\ldots\) (repeated \(n\) times) - the program to draw one straight segment of the spiral.
  • Hint 7
    Have 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.foo[email protected]. Please do not write to this address regarding general admissions or course queries.