Question $3$

$(/22$ marks$).$

i$)$ Write a recursive algorithm $($in pseudo$-$code$)$ that for a non$-$negative integer $n$ computes the $n-$th element in the sequence:

$f(0)=1,$

$f(1)=1,$

$f(2)=2,$

$f(3)=5,$

$f(4)=10,$

$f(5)=19,$

$f(n)=2f(n-1)-f(n-2)+2f(n-3).$

ii$)$ Use you pseudo$-$code to compute $($by hand$)f(7).$ Please show all the recursive calls to your algorithm.

Note: You MUST provide the inputs and output at the beginning of the algorithm.