Fibonacci Algorithms and their different manifestations. Which is the best?

[Rooks Forgenal]

GOALS:
The function will accept only one parameter (that of 'n').
The function uses nothing but temporary variables (function variables)
The function returns the correct Fibonacci number at the passed index (i.e. x_fibonacci(0) = 1)
The function must accept a parameter from 0 to 30 and produce the correct answer.

The first is a recursive function. I would love some constructive criticism on this code. My recursive abilities are pretty rusty.

	public int a_fibonacci(int n, int... values) {
		int err_ansr;
		if (n < 0) {
			err_ansr = -1;
		} else if (values.length > 0 && values[2] == n) {
			return Math.min(values[0], values[1]);
		} else if (values.length == 0) {
			err_ansr = a_fibonacci(n, 1, 1, 0, 0);
		} else if (values[3] == 0) {
			values[0] = values[0] + values[1];
			err_ansr = a_fibonacci(n, values[0], values[1], values[2] + 1, 1);
		} else {
			values[1] = values[0] + values[1];
			err_ansr = a_fibonacci(n, values[0], values[1], values[2] + 1, 0);
		}
		return err_ansr;
	}

The second version is as simple as I could think to make it. It just steps forward and was reminiscent of a bubble sort algorithm. I wonder if it can be made better? I did it kind of fast.

	public int b_fibonacci(int n) {
		if (n < 0) {
			return -1;
		}else if(n == 0) {
			return 1;
		}
		n--;
		int front = 1;
		int back = 1;
		int temp;
		for (int i = 0; i < n; i++) {
			temp = front;
			front = back + front;
			back = temp;
		}
		return front;
	}

This one is my favorite. It is a fine example of why direct translation of mathematics to code can get VERY bulky. However, it adds some usefulness by allowing a user access to combinatorial mathematics. If you were to look at this for the purpose of making it better, what would you change?

	public int c_fibonacci(int n) {
		if (n < 0) {
			return -1;
		} else if(n == 0) {
			return 1;
		}
		int sum = 0;
		for (int i = 0; i < n; i++) {
			sum = sum + nChooseK((n - i), i);
		}
		return sum;
	}

	public int nChooseK(int n, int r) {
		int answer;
		if (r > n) {
			return 0;
		} else if (r == 0 || n == 0 || n == r) {
			return 1;
		}
		if (r > n / 2) {
			r = n - r;
		}
		long numerator = 1;
		long denominator = 1;
		for (int i = n; i > (n - r); i--) {
			numerator = numerator * i;
		}
		for (int i = r; i > 2; i--) {
			r = r * (i - 1);
		}
		denominator = r;
		answer = (int) (numerator / denominator);
		return answer;
	}

Why would I make these and post them to the forum? Well the last Fibonacci post was in 2003 and I was bored.

[Sebastian Janisch]

Hey,

the recursive method could be a bit shorter ;-) ...

private static int fibonacci(int a)
{
    if (a==1 || a==2)
    { 
        return 1;
    }
    else
    {
        return fibonacci (a-1) + fibonacci(a-2);
    }
}

The problem with this recursive method is the following.

Imagine you pass 5. Then in the first cycle, fibonacci is again called for the value 4 (a -1) and 3 (a-2). Again in the next cycle you would call with a value of 3 (a-1) and 2 (a-2). You see that there are redundant method calls, which easily add up. Even though a recursive approach might seem as the more elegant one, in practice it mostly is the one you would not opt for compared to an iterative approach. You add up stack over stack, causing the process to slow down and risking to run into a StackOverflowError ...

[Rooks Forgenal]

Oh snap. Talk about an improvement!

[Paul Clapham]

If you want to try something completely different, you could try writing a program which uses this:

Fibonacci_number#Closed_form_expression

[Rooks Forgenal]

I have to think that due to round off error, I could never truly get a reliable answer. I think I could do it if I used Scheme because it keeps things like root 5 as fractional instead of decimal. Even so, I think the round off would bite me in the end (unless I just Math.round(n);)

Also, I ran the more succinct solution given by Sebastian Janisch and it is noticeably slower at indexes > 40 than my recursive algorithm. Does anyone know how to calculate Big(O) of each to see why that is? I had to fix it to fit the requirements and it might be my change that caused the problem.

	public int d_fibonacci(int n) {
		if (n < 0) {
			return -1;
		} else if (n == 0 || n == 1) {
			return 1;
		} else {
			return d_fibonacci(n - 1) + d_fibonacci(n - 2);
		}
	}

Times in nano seconds were:
a_fibonacci = 36,000
b_fibonacci = 6,100
c_fibonacci = 17,515
d_fibonacci = 11,606,422,821

If anyone can explain the difference I would be very happy. Thanks in advance.

[Campbell Ritchie]

As you will see from Sebastian Janisch's reply, you have a subtle error in your assignment; fib(0) is not 1 but 0. You should have fib(1) = 1 and fib(2) = 1 in the commonest Fibonacci series, and fib(10) = 55. work out why he has marked the method static, which I believe is correct.
Note you can shorten SJ's solution to one statement and avoid two returns in the same method:
return a == 1 || a == 2 ? 1 : fib(a - 1) + fib(a - 2);

It is possible to pass two parameters to a Fibonacci method and have it run in linear time, and it is possible to pass 4 parameters and run in logarithmic time (reference on this thread), but I can't remember how to do it at the moment.

[Campbell Ritchie]

I would change your method:

	public int d_fibonacci(int n) {
		if (n < 0) {
			throw new IllegalArgumentException("Negative indices not accepted for Fibonacci numbers"); //This line.
		} else if (n == 0 || n == 1) {
			return 1;
		} else {
			return d_fibonacci(n - 1) + d_fibonacci(n - 2);
		}
	}

[Campbell Ritchie]

The recursive method runs in 1.618^n time. I shall let you work out where the 1.618 comes from.

You almost certainly won't suffer stack overflow or memory lack, however; values are taken off the stack almost as fast as they are put on it.
The way to get a method taking a single parameter and run in linear time is to pass that parameter on to a private helper method which takes two parameters and does the actual recursion.

[fred rosenberger]

I would say the first implementation is the worst, because it doesn't meet the specifications:

The function will accept only one parameter (that of 'n').

public int a_fibonacci(int n, int... values)