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?

Solution 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)

Solution 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.

Solution 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 )

Solution 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.

Solution 5

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.

View more solutions

Comments

[Nixit Patel]

is it 3*(f(n - 1) - f(n - 2)) or (3*f(n-1))-f(n - 2)

[sarnold]

@nixit: it is usually safe to assume * has a higher precedence than + -- I think APL (and derived languages) and Smalltalk are the only languages that do not assign * a higher precedence than +. (Though one could argue that RPN also doesn't have higher precedence for * than +, but only because there are no precedence rules for RPN...)

[Nixit Patel]

@sarnold yeah I know that but if we put value of 0 in to f(n) then the value I got is -1 so I get confused

[sarnold]

@nixit: the unstated assumption here is that f(n) is defined only for non-negative integers and the formula f(n) = 3 * f(n-1) - f(n-2) is to be used only for integers greater than or equal to 2. f(0) gives you the result 1 by definition.

[ikegami]

Only tail-recursive algorithms (and those that can be made tail-recursive) can be converted into iterative ones. The OP's algorithm cannot be made iterative. That doesn't mean there isn't an iterative algorithm that can do the same thing, though.

[Louis Wasserman]

I'm not sure I buy the distinction you're making. The OP didn't provide an algorithm; he provided a recursive definition, which @paxdiablo demonstrated can be computed iteratively.

[ypercubeᵀᴹ]

@paxdiablo: It should be for i = 1 to n-1 or for i=2 to n. Right?

[paxdiablo]

@ypercube: yes, I relooked at that and I think the 2..n you proposed makes more sense.

[paxdiablo]

@ikegami, all recursive algorithms can be made iterative, if only by virtue of the fact you can manage your own data stack rather than using the function stack. I suspect you mean tail recursion is easier for a compiler to convert to iteration.

[ikegami]

@Louis Wasserman, paxdiablo has greatly edited his post since I wrote that, but the statement to which I commented is still there: "all recursive algorithms can be converted into iterative ones".

[Yonatan N]

@ikegami: You're correct, but for entirely the wrong reason. All computable functions can be converted to tail-recursive algorithms (whether that can be done efficiently is a different question... consider a recursive implementation of a TM simulator), so yes... only those functions that can be made tail-recursive can be made iterative -- just like all algorithms.

[ikegami]

@paxdiablo, Doing your own recursion instead of using the compiler's is still recursion. You're arguing that an algorithm is or isn't recursive based on how a coder will eventually implement it, and that makes no sense unless you're arguing there's no such thing as a recursive algorithm (just recursive code).

[paxdiablo]

@ikegami, I would consider that a disagreement in semantics :-) I define recursion as using the function-calling aspects of the language to handle the levels. Others may consider a non-recursive (using my definition) single-level function maintaining it's own stack to be recursion as well. I don't, but I can see your viewpoint, and it's a valid one. The usual reason for converting recursion to iteration is because the function stack is often more limited than a data stack you can put together. It's especially useful in this case since you only need a "stack" of size 3.

[Voo]

@ikegami There's a clear definition of what "recursion" means in CS. You may use your own, but don't be surprised if most people won't understand what you're going on about. (That's not saying your definition is wrong - but the reason we have conventions about these things is so that we can talk about things without having to start from the ground every time)

[Voo]

O(N) space solution for something that can easily be solved in O(1)? Not happy with that.

[ikegami]

@ikegami, "I would consider that a disagreement in semantics". I agree fully: your semantics are contradicting themselves. Your definition of recursive makes it impossible for there to be "recursive algorithms", yet you said certain properties apply to recursive algorithms.

[Reinstate Monica]

You mean (130.5-3)/(2*130.5)*((3-130.5)/2)**n + (0.5+3/(2*130.5))*((3+13**0.5)/2)**n)

[Miserable Variable]

I don't know but given that you are WolframH I must mean that

[ikegami]

@Voo, Oddly, wikipedia doesn't have a CS-specific definition. It just gives examples which aren't clear. What would you say is the definitions of "recursive algorithm" and "recursive function"?

[ikegami]

@Voo, More importantly, what do you think the OP wants? If he wants to elimiate recursion, it's probably because he wants to eliminate the cost of recursion. And simply creating your own recursive stack does not do that. So not only does paxdiablo contradict himself, the statement you are backing up is completely unhelpful.

[Voo]

@ikegami Well I'm somewhat tempted to look it up in TAOCP and stuff, but for now I'd go with the simple "function that solves a problem by splitting the problem into smaller sub problems and repeatedly calling itself". That seems to encompass the most important traits. About the second part: Clearly for such a simple problem the given iterative solution is preferable, but there are other problems where we just want to get the overhead down (much less to store in our own datastructure, faster) and avoid StackOverflows.

[Reinstate Monica]

It's f(n), and it doesn't evaluate f(n-1) and f(n-2), and I am a mathematician - hopefully it's clear now :-)

[sarnold]

Man, I wrote Perl for years a few years back and I find this code hard to grok on the first go. Perl may be many things, but legible isn't really one of them. (This appears to suffer from the same O(N) space that ElKamina's answer requires, but yours is kind enough to store the results for later use.)

[sarnold]

The original question is a slight modification of Fibonacci; is this for the original Fib or is this for the slight modification?

[ypercubeᵀᴹ]

@sarnold: fibonacci(n) is the Fibonacci. f(n) is the asked sequence.

[Miserable Variable]

I wasn't being sarcastic, this is exactly what I was asking. Thanks :)

[ElKamina]

@Voo The question does not require O(1) space solution. This solution should be faster because of avoiding two (measly) assignment statements :D

[Voo]

Umn.. no, that solution will be much, much slower - except if the compiler can prove that we don't need the array (in which case we get pax's solution). If we have the array we have N+1 stores to memory and 2N reads from memory instead of computing the whole thing in registers. Much, much slower as I said :)

[paxdiablo]

I love the wikipedia quote "If you already know what recursion is, just remember the answer, otherwise, find someone who is standing closer to Douglas Hofstadter than you are; then ask him or her what recursion is". Having said that, I think we should shut down the discussion (or move it to the discussion area). To (mis)quote BillG: "15 comments should be enough for any answer" :-)

[paxdiablo]

@WolframH, you should put that in an answer (along with some modicum of proof or support). It is a non-recursive solution, assuming it's right which I have no reason to doubt, though no massive desire to confirm :-) It may well be better than the iterative solutions for large enough values of n (including mine) so is worth an upvote at least.

[ElKamina]

@Voo Sure paxdiablo's solution is better than mine (I up-voted for it). But this solution, although not optimal, is still valid.

[Ben Voigt]

Proof is easy (use induction).

[Ben Voigt]

One could also find the eigenvalues and use the characteristic equation to evaluate the matrix power in terms of lower matrix powers... oh wait.

[ikegami]

@Voo, You missed the most important part of the question. You defined recursive function, but we're talking about recursive algorithms. So again, what's this well known definition of recursive algorithm?

[paxdiablo]

The advantage of this solution is that you can remember the values calculated (by putting the array outside of the function and possibly keeping track of where you've calculated up to). This could greatly speed up future calculations.

[paxdiablo]

I think as long as the limitations are known (and documented), it's still a valid solution. For example, the Java (signed) long type can only handle up to n=46 anyway. n=23 is the limit for signed and unsigned 32-bit int. Just one thing I'd mention is that you've added the second term rather than subtracting it. I'd still be interested in how you got from the rules to the expression, and the Wikipedia page showing how to do that for fib(n) gives me a headache :-)

[GameZelda]

WolframAlpha link

[Reinstate Monica]

@GameZela, that link doesn't work for me, some characters are swallowed. But yes, wolframalpha is one good way to solve. I did it at least partly by hand. en.wikipedia.org/wiki/Recurrence_relation explains how to do it - it is a (simple) special case, described under "general methods".

[Reinstate Monica]

@paxdiablo, you're right, I mixed up + and -... so this solves a different problem. If you want the right solution, just use wolframalpha as suggested by GameZelda.

[paxdiablo]

"should be readable enough to a Java developer" - only one that's had a frontal lobotomy, I suspect. Perl code is often unreadable to everyone, including Perl developers, I've seen it described before as a write-only language :-) Just kidding BTW, this isn't too bad and I do write the occasional Perl snippet.

[Sprague]

The OP probably means 'a solution which doesn't eventually exhaust the stack in non-TCO-implementing languages', which is what most people think when they hear "non-recursive".

[Aaron Franke]

How do we know how to write the iterative function if we start with a recursive one?

[Aaron Franke]

How do we know how to transform the solutions into iterative ones? What if I have more than 2 starting values?

[Óscar López]

You add more variables. Each problem is different, if you have a concrete example, please post it as a new question.