Let $f$ be the recursive function below, with $f(1)=f(0)=0$. What is the value of $f(1337)$? $$ \begin{aligned} & 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{aligned} $$
  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)?$

$n$ appears only in the argument of $f$. Concentrate first only on the argument of $f$, going down from 1337.

Pay attention to the numbers you subtract (subtractors) each time. You may want to subtract sufficiently many.

Can you spot a group of subtractors that repeats? How many groups are there?

Now concentrate on what happens outside the argument of $f$. What value is added in each group?

Pay attention to the final terms of the recursion.

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{aligned} 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{aligned} $$