What is a non recursive solution for Fibonacci-lik

问题:

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?

回答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)

回答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.

回答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 )

回答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.

回答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];
}

回答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.

回答7:

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]

回答8:

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

回答9:

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]

回答10:

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.