What is a non recursive solution for Fibonacci-like sequence in Java?

Question

Given this pseudo code of a function

f(0) = 1; 
f(1) = 3; 
f(n) = 3 * f(n - 1) - f(n - 2); // for n >= 2.

Is there a non recursive way of doing this?

Answer 1

Yes, all recursive algorithms can be converted into iterative ones. The recursive solution to your problem is something like (pseudo-code):

def f(n):
    if n == 0: return 1
    if n == 1: return 3
    return 3 * f(n-1) - f(n-2)

Since you only have to remember the previous two terms to calculate the current one, you can use something like the following pseudo-code:

def f(n):
    if n == 0:
        return 1
    if n == 1:
        return 3
    grandparent = 1
    parent = 3
    for i = 2 to n:
        me = 3 * parent - grandparent
        grandparent = parent
        parent = me
    return me

This simply handles the "recursive" termination condition first then iterates where it would normally call itself. At each iteration, you calculate the current term, then rotate the terms through the grandparent and parent.

There is no need to keep the grandparent around once you've calculated the current iteration since it's no longer used.

In fact, it could be said that the iterative solution is better (from a performance viewpoint) since terms are not recalculated as they are in the recursive solution. The recursive solution does have a certain elegance about it though (recursive solutions generally do).

---

Of course, like the Fibonacci sequence, that value you calculate rises very quickly so, if you want what's possibly the fastest solution (you should check all performance claims, including mine), a pre-calculated lookup table may be the way to go.

Using the following Java code to create a table of long values (that while condition is just a sneaky trick to catch overflow, which is the point at which you can stop building the array):

class GenLookup {
    public static void main(String args[]) {
        long a = 1, b = 3, c;
        System.out.print ("long lookup[] = { " + a + "L, " + b + "L");
        c = 3 * b - a;
        while ((c + a) / 3 == b) {
            System.out.print (", " + c + "L");
            a = b; b = c; c = 3 * b - a;
        }
        System.out.println (" };");
    }
} 

gives you an array definition that you can just plug in to a lookup function, as per the following example:

public static long fn (int n) {
    long lookup[] = { 1L, 3L, 8L, 21L, 55L, 144L, 377L, 987L, 2584L, 6765L,
        17711L, 46368L, 121393L, 317811L, 832040L, 2178309L, 5702887L,
        14930352L, 39088169L, 102334155L, 267914296L, 701408733L,
        1836311903L, 4807526976L, 12586269025L, 32951280099L, 86267571272L,
        225851433717L, 591286729879L, 1548008755920L, 4052739537881L,
        10610209857723L, 27777890035288L, 72723460248141L, 190392490709135L,
        498454011879264L, 1304969544928657L, 3416454622906707L,
        8944394323791464L, 23416728348467685L, 61305790721611591L,
        160500643816367088L, 420196140727489673L, 1100087778366101931L,
        2880067194370816120L, 7540113804746346429L };

    if ((n < 1) || (n > lookup.length))
        return -1L;

    return lookup[n-1];
}

---

Interestingly enough, WolframAlpha comes up with a formulaic approach that doesn't even use iteration. If you go to their site and enter f(0)=1, f(1)=3, f(n)=3f(n-1)-f(n-2), you'll get back the formula:

Unfortunately, it may not be as fast as the iteration, given the limited number of input values that result in something that can fit in a Java long, since it uses floating point. It's almost certainly (but, again, you would need to check this) slower than a table lookup.

And, it's probably perfect in the world of maths where real-world limits like non-infinite storage don't come into play but, possibly due to the limits of IEEE precision, it breaks down at higher values of n.

The following functions are the equivalent of that expression and the lookup solution:

class CheckWolf {
    public static long fn2 (int n) {
        return (long)(
            (5.0 - 3.0 * Math.sqrt(5.0)) *
                Math.pow(((3.0 - Math.sqrt(5.0)) / 2.0), n-1) +
            (5.0 + 3.0 * Math.sqrt(5.0)) *
                Math.pow(((3.0 + Math.sqrt(5.0)) / 2.0), n-1)
            ) / 10;
    }

    public static long fn (int n) {
        long lookup[] = { 1L, 3L, 8L, 21L, 55L, 144L, 377L, 987L, 2584L, 6765L,
            17711L, 46368L, 121393L, 317811L, 832040L, 2178309L, 5702887L,
            14930352L, 39088169L, 102334155L, 267914296L, 701408733L,
            1836311903L, 4807526976L, 12586269025L, 32951280099L, 86267571272L,
            225851433717L, 591286729879L, 1548008755920L, 4052739537881L,
            10610209857723L, 27777890035288L, 72723460248141L, 190392490709135L,
            498454011879264L, 1304969544928657L, 3416454622906707L,
            8944394323791464L, 23416728348467685L, 61305790721611591L,
            160500643816367088L, 420196140727489673L, 1100087778366101931L,
            2880067194370816120L, 7540113804746346429L };
        if ((n < 1) || (n > lookup.length)) return -1L;
        return lookup[n-1];
    }

Now we need a mainline to compare them:

    public static void main(String args[]) {
        for (int i = 1; i < 50; i++)
            if (fn(i) != fn2(i))
                System.out.println ("BAD:  " + i + ": " + fn(i) + ", " + fn2(i)
                    + " (" + Math.abs(fn(i) - fn2(i)) + ")");
            else
                System.out.println ("GOOD: " + i + ": " + fn(i) + ", " + fn2(i));
        }
    }

This will output:

GOOD: 1: 1, 1
GOOD: 2: 3, 3
GOOD: 3: 8, 8
GOOD: 4: 21, 21
GOOD: 5: 55, 55
GOOD: 6: 144, 144
GOOD: 7: 377, 377
GOOD: 8: 987, 987
GOOD: 9: 2584, 2584
GOOD: 10: 6765, 6765
GOOD: 11: 17711, 17711
GOOD: 12: 46368, 46368
GOOD: 13: 121393, 121393
GOOD: 14: 317811, 317811
GOOD: 15: 832040, 832040
GOOD: 16: 2178309, 2178309
GOOD: 17: 5702887, 5702887
GOOD: 18: 14930352, 14930352
GOOD: 19: 39088169, 39088169
GOOD: 20: 102334155, 102334155
GOOD: 21: 267914296, 267914296
GOOD: 22: 701408733, 701408733
GOOD: 23: 1836311903, 1836311903
GOOD: 24: 4807526976, 4807526976
GOOD: 25: 12586269025, 12586269025

Looking good up to here, some more:

GOOD: 26: 32951280099, 32951280099
GOOD: 27: 86267571272, 86267571272
GOOD: 28: 225851433717, 225851433717
GOOD: 29: 591286729879, 591286729879
GOOD: 30: 1548008755920, 1548008755920
GOOD: 31: 4052739537881, 4052739537881
GOOD: 32: 10610209857723, 10610209857723
GOOD: 33: 27777890035288, 27777890035288
GOOD: 34: 72723460248141, 72723460248141
GOOD: 35: 190392490709135, 190392490709135
GOOD: 36: 498454011879264, 498454011879264

But then something starts going awry:

BAD:  37: 1304969544928657, 1304969544928658 (1)
BAD:  38: 3416454622906707, 3416454622906709 (2)
BAD:  39: 8944394323791464, 8944394323791472 (8)
BAD:  40: 23416728348467685, 23416728348467705 (20)
BAD:  41: 61305790721611591, 61305790721611648 (57)
BAD:  42: 160500643816367088, 160500643816367232 (144)
BAD:  43: 420196140727489673, 420196140727490048 (375)

The fact that the above are tantalisingly close, and that the number of digits in the error is proportional to the number of digits in the result, indicates it's probably a loss-of-precision problem.

After this point, the formulaic function just starts returning the maximum long value:

BAD:  44: 1100087778366101931, 922337203685477580 (177750574680624351)
BAD:  45: 2880067194370816120, 922337203685477580 (1957729990685338540)
BAD:  46: 7540113804746346429, 922337203685477580 (6617776601060868849)

And then our lookup function breaks down as well since the numbers are too big for a long:

BAD:  47: -1, 922337203685477580 (922337203685477581)
BAD:  48: -1, 922337203685477580 (922337203685477581)
BAD:  49: -1, 922337203685477580 (922337203685477581)

Answer 2

Answers here are correct, but they work in O(n), while you can do it in O(log n), exponentially faster. Observe that

[f(n)  ] = [3 -1] [f(n-1)]
[f(n-1)]   [1  0] [f(n-2)]

Let v_n be the vector [f(n), f(n-1)] and A the matrix as above, so you get v_n = A v_n-1, therefore v_n = A^n-1 v₁. Compute (n-1)-th power of matrix A using binary exponentiation and multiply it by v₁. For more on linear recurrences see here.

Answer 3

If your question is about whether an equivalent non-recursive definition of the function can be found, you should search for properties of the Fibonacci sequence.

Your sequence can be found by writing the Fibonacci (without the first 2 numbers) and removing every 2nd number: 1, 3, 8, 21, 55, 144, ...

sqrt5 = sqrt(5)
phi = ( 1 + sqrt5 ) / 2
fibonacci(n) = round( power( phi, n ) / sqrt5 ) 
f(n) = fibonacci( 2*n + 2 )

Answer 4

It's simple, in Java the solution looks like this:

public int f(int n) {

      int tmp;
      int a = 3;
      int b = 1;

      for (int i = 0; i < n; i++) {
          tmp = a;
          a = 3 * a - b;
          b = tmp;
      }

      return b;

}

All recursive solutions can be transformed into iterative solutions (the opposite is also true, see this post), albeit it's easier if the recursive solution it's in tail-recursive form.

The above algorithm can be understood as a dynamic-programming solution to the original recursion, it's very efficient since it only needs to save the two previous values at each point in the iteration.

Answer 5

[ Oops, I thought this was a Perl question. Still, the code should be readable enough to a Java developer. ]

This is really just moving the recursion to userland, but you could use:

sub f { 
    my ($n) = @_;
    my @f = (1,3);
    $f[$_] = 3 * $f[$_-1]- $f[$_-2] for 2 .. $n;
    return $f[$n];
}

Of course, this begs for caching. There's no need to recalculate values we already know.

my @f = (1,3);
sub f { 
    my ($n) = @_;
    $f[$_] = 3 * $f[$_-1]- $f[$_-2] for @f .. $n;
    return $f[$n];
}

Answer 6

The function is defined in terms of itself, so in one sense any implementation is recursive, unless some mathematician comes and tells us f(n) can be evaluated without evaluating f(n-1) and f(n-2). As others have shown, there is a way to implement it in Java function that does not call itself.

Answer 7

The Fibonacci series sequence of numbers starts as: 0,1,1,2,3,5,8,13,21,34,55....

this can be defined by simple recurrence relation F(n)=F(n-1)+F(n-2) for n>1 and two initial conditions, F(0)=1 and F(1)=1

Algorithm Fibonacci

//Computes the nth Fibonacci number

//Input: A non-negative integer

//Output: The nth Fibonacci number

1. Begin Fibo
2. integer n, i;
3.    if n<=1 then
4.     return n;
5.  else
6.    F(0)<-0; F(1)<-1;
7.    for i<-2 to n do
8.     F(i)<-F(i-1)+F(i-2);
9.     F(i-2)=F(i-2);
10.    F(i-1)=F(i);
11. done
12. end if
13. end Fibo

Answer 8

Here is simply a function with minimum line of code and maximum flexibility.

You can add any "initial values" and any other recursive "function" you want simply.

def fib(n):
  fibs = [1, 3]       # <--  your initial values here 
  if n == 1:
    return fibs[0]
  if n == 2:
    return fibs[:1]
  for i in range(2, n):
    fibs.append(3*fibs[-1] - fibs[-2])  # <-- your function here
  return fibs

And the result is:

n=10
print(fib(n))

[1, 3, 8, 21, 55, 144, 377, 987, 2584, 6765]

Answer 9

This is my non-recursive solution (javascript):

function fibonacci(n) {
  let f = 0;
  let g = 1;
  for (let i = 0; i <= n; i++) {
    console.log(f);
    f = f + g;
    g = f - g;
  }
}

fibonacci(10);

Answer 10

def func(n):
    f= array(n+1)
    f[0]=1
    f[1]=3

    for i in 2:n :
        f[i] = 3*f[i-1]-f[i-2]
    return f[n]

Answer 11

I don't know why nobody has proposed the following algorithm, which is way simpler and faster:

class Fibonacci {

    public void compute(int n) {
        long i=0;
        long a=0,b=1,d=0;

        while (i<n) {

            System.out.println(a);
            d=a;
            a=b;
            b=b+d;
            i+=1;
        }
    }

    public static void main(String[] args) {
    
        var fib = new Fibonacci();

        fib.compute(90);
    }

}

Output:

0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657
46368
75025
121393
196418
317811
514229
832040
1346269
2178309
3524578
5702887
9227465
14930352
24157817
39088169
63245986
102334155
165580141
267914296
433494437
701408733
1134903170
1836311903
2971215073
4807526976
7778742049
12586269025
20365011074
32951280099
53316291173
86267571272
139583862445
225851433717
365435296162
591286729879
956722026041
1548008755920
2504730781961
4052739537881
6557470319842
10610209857723
17167680177565
27777890035288
44945570212853
72723460248141
117669030460994
190392490709135
308061521170129
498454011879264
806515533049393
1304969544928657
2111485077978050
3416454622906707
5527939700884757
8944394323791464
14472334024676221
23416728348467685
37889062373143906
61305790721611591
99194853094755497
160500643816367088
259695496911122585
420196140727489673
679891637638612258
1100087778366101931
1779979416004714189

Answer 12

As requested by @paxdiablo I'm making this an answer. It's a recurrence relation and can be solved non-recursively, similar to the fibonacci sequence mentioned in another answer. It turns out to be (Python notation).

def f(n):
    return int((13**0.5-3)/(2*13**0.5)*((3-13**0.5)/2)**n + (0.5+3/(2*13**0.5))*((3+13**0.5)/2)**n)

However, this forumula does most probably not work for large n, because of limited float precision. The given python version fails for n = 30:

>>> print ([f(n) == 3 * f(n-1) + f(n-2) for n in range(2, 30)])
[True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, False]
>>> print([f(n) for n in range(30)])
[1, 3, 10, 33, 109, 360, 1189, 3927, 12970, 42837, 141481, 467280, 1543321, 5097243, 16835050, 55602393, 183642229, 606529080, 2003229469, 6616217487, 21851881930, 72171863277, 238367471761, 787274278560, 2600190307441, 8587845200883, 28363725910090, 93679022931153, 309400794703549, 1021881407041801]

Warning: I used a "+" instead of a "-", so the formula is wrong. See comments.