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 1 Question 19

Let \(f\) be the recursive function below, with \(f(1)=f(0)=0\). What is the value of \(f(1337)\)? \[ \begin{array}{l} f(n)=f(n-1)-1 \qquad\text{ if $n$ is divisible by 2 or 3 }\\ f(n)=f(n-2)+2 \qquad\text{ otherwise} \end{array} \]

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

Warm-up Questions

  1. Convert the recursive function \(f(n)=f(n-1)+1,\) with \(f(0)=0\) into a non-recursive form.
  2. Consider the incomplete recursive function \(f(n)=2f(n-1)\). What mathematical function could it implement and how would you make it complete?
  3. Let \(f(n)=f(n-3)+1\) with \(f(n)=0\) for \(n<0\). What is \(f(90)?\)

Hints

  • Hint 1
    \(n\) appears only in the argument of \(f\). Concentrate first only on the argument of \(f\), going down from 1337.
  • Hint 2
    Pay attention to the numbers you subtract (subtractors) each time. You may want to subtract sufficiently many.
  • Hint 3
    Can you spot a group of subtractors that repeats? How many groups are there?
  • Hint 4
    Now concentrate on what happens outside the argument of \(f\). What value is added in each group?
  • Hint 5
    Pay attention to the final terms of the recursion.

Solution

We begin by tracing the recurrence. Since \(n\) appears only in the argument of \(f\), we can concentrate first only on what happens with the argument as it goes down from 1337. Firstly, \(1337\) is not divisible by \(2\) or \(3\), hence we have:

  • \(1337-2=1335\) which is divisible by \(3\), then
  • \(1335-1=1334\) which is divisible by \(2\), then
  • \(1334-1=1333\) which is not divisible by \(2\) or \(3\), then
  • \(1333-2=1331\) which is not divisible by \(2\) or \(3\), then
  • \(1331-2=1329\) which is divisible by \(3\), then
  • \(1329-1=1328\) which is divisible by \(2\), ...

We notice that the sequence \((-2,-1,-1,-2)\) of subtractors repeats every \(6\) integers. The number of times this happens is \(\lfloor1337/(2+1+1+2)\rfloor=222\) times. This gives a remainder of 5, which we need to keep in mind.

We're done with the argument of \(f\). In terms of its value, every time the argument goes to \(-2\) the value increases with \(2\), and every time the argument goes to \(-1\) the value decreases with \(1\). Hence we have: \[ \begin{align} f(1337) &=222(+2-1-1+2)+f(5)\\ &=444+f(3)+2\\ &=444+f(2)-1+2\\ &=444+f(1)-1-1+2\\ &=444 \end{align} \]

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.