Задачка

Именно хвостовую, а не tree-

int
rec_func(int a, int b, int c, int n)
{
    switch(n)
    {
    case 0:
        return a;
    case 1:
        return b;
    case 2:
        return c;
    default:
        return rec_func(b, c, 3 * a + 2 * b + c, n - 1);
    }
}

int
func(int n)
{
    return rec_func(0, 1, 2, n);
}

Первое что приходит в голову - написать циклом одновременно запоминая 3 последовательных члена, а затем цикл преобразовать в хвостатую рекурсию

А еще как-то можно через матрицы, тогда наверное можно и за O(Log(n))сделать.

Чёрт возьми, как оказалось легко!

SICP? ;)

/x_n    \       /x_(n-1)\
|x_(n-1)| = W*  |x_(n-2)|
\x_(n-2)/       \x_(n-3)/


          /1 2 3\
Где W =   |1 0 0|
          \0 1 0/

Задача сводится к вычислению W^(n-3)
Кассмотрим воследовательность 
W^1 W^2 W^4 W^8 W^16.....

Получаем что W^(n-3) = f(E,W,n-3), где
          
f(R,W,n) | = R если n = 0 
         | = f(R*W,W^2,k) если n=2*k+1
         | = f(R, W^2,k) если n=2*k

Долго, зато за O(Log(n)) а не за O(n)

ага