Iterative Version of Modified Fibonacci Sequence

Question

I was just going through the iterative version of fibonacci series algorithm. I found this following code

int Fibonacci(int n)
{
   int f1 = 0;
   int f2 = 1;
   int fn;
   for ( int i = 2; i < n; i++ )
   {
      fn = f1 + f2;
      f1 = f2;
      f2 = fn;
   }
}  

A silly question just raised in my mind. The function above adds two previous numbers and returns the third one and then get variables ready for the next iteration. What if it would be something like this. "Return a number of series which is the sum of previous three numbers" how we can change the above code to find such a number.u

Answer 1

As a hint, notice that the above algorithm works by "cycling" the numbers through some variables. In the above code, at each point you are storing

 F_0    F_1
  a      b

You then "shift" them over by one step in the loop:

 F_1    F_2
  a      b

You then "shift" them again in the next loop iteration:

 F_2    F_3
  a      b

If you want to update the algorithm sum the last three values, think about storing them like this:

 T_0    T_1    T_2
  a      b      c

Then shift them again:

 T_1    T_2    T_3
  a      b      c

Then shift them again:

 T_2    T_3    T_4
  a      b      c

Converting this intuition into code is a good exercise, so I'll leave those details to you.

That said - there is a much, much faster way to compute the nth term of the Fibonacci and "Tribonacci" sequences. This article describes a very clever trick using matrix multiplication to compute terms more quickly than the above loop, and there is code available here that implements this algorithm.

Hope this helps!

Answer 2

I like recursion. Call me a sadist.

static int rTribonacci (int n, int a, int b, int c) {
    if (n == 0) return a;
    return rTribonacci (n-1, b, c, a + b + c);
}

int Tribonacci (int n) { return rTribonacci(n, 0, 0, 1); }