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