How to determine the nth Fibonacci number?

[flyingcurry]

We have an assignment to write a program finding the nth Fibonacci number.
On the web, there are some standard mathematical equations for this, but that would just defeat the purpose of this assignment if I use those formulas.

I have my current code down here(with some sketchy back up code stuff), but I am really confused about what I am writing down here, the loop I have written in my code is not really working at all. :|

Also, would this program represent a linear equation or a quadratic or possibly polynomial equation?

import java.util.InputMismatchException;
import java.util.Scanner;


public class FibonacciNumbers {

	/**
	 * @param args
	 */

	static int nthNumber;

	public static int fibonacciCalculate (int n) {

		int i;
		int [] x = new int[n];
		x[0]=1;
		x[1]=1;
		/*for (i=0; i<n; i++)
		{
			x[i+2]=x[i]+x[i+1];
		}*/

		for (i=2; i<n-1; i++)
		{
			x[n] = x[n-2]+x[n-1];
		}

		nthNumber=x[n-1];
		return nthNumber;//returns the result to the main method, terminates fibonacciCalculate method
	}


	public static void main(String[] args) {
		// TODO Auto-generated method stub

		int n = 0;
		Scanner sc = new Scanner (System.in);

		boolean checkException = false;//create a boolean variable called "checkException"
		   //and initiate its default value

		do {
			System.out.println("Enter an integer n for the nth Fibonacci number you want to find: ");
			try {
				n = sc.nextInt();
				checkException = true;//sets the boolean value to true, will cause
				//the do-while loop to exit
			}

			catch (InputMismatchException e)//catches all number format exceptions
			{
					System.out.println("Invalid data. Please enter an integer that is greater than 0.");
					checkException = false;//sets boolean value to false, continues the loop
			}

			try {


				nthNumber= fibonacciCalculate (n);//calls the fibonacciCalculate method to obtain
				//the integer nthNumber, the nth Fibonacci number
				checkException = true;
			}
			catch (ArrayIndexOutOfBoundsException a)
			{
				System.out.println("ohlalaInvalid data. Please enter an integer that is greater than 0.");
				checkException = false;//sets boolean value to false, continues the loop
			}

		} while (checkException == false || n<=0);//remains in loop as long as the boolean variable is false

		switch(n)
		{
		case 1: System.out.println("Your first Fibonacci number is "+nthNumber);
		break;
		case 2: System.out.println("Your second Fibonacci number is "+nthNumber);
		break;
		case 3: System.out.println("Your third Fibonacci number is "+nthNumber);
		break;
		default : System.out.println("Your "+n+"th Fibonacci number is "+nthNumber);
		break;
		}


	}

}

[coil]

Try doing it with recursion. The base case would be n=1 or n=2, in which case return 1 - the first two numbers of the sequence are 1. For everything else, the nth term is the previous two terms' sum - find those with recursive calls.

[jon.kiparsky]

And remember, you can't recurse without cursing first.

If you're not familiar with recursion, it'll seem weird at first, but really it's just another method call, only your method calls itself. The only trick is knowing where to stop. As coil says, you have two possibiliities: either you know the answer, and it's 1, or you don't and you have to get some help. If you know the answer and it's one, just say "one" and go sit down. If you don't know that the answer is one, it's not one, but you do know that it's n greater than the previous number, so you if you had a function that would tell you what the previous number was, you'd be set. And you do have that function - you're writing it right now! So call it to get the previous value in the series, add the current n, and return that total.

Totally weird if you haven't done it before, but it really is that simple. And once you've done that, you're ready to tackle Lisp! Well, sorta, kinda. Ready-ish.

[extemer]

class FibTest {
	public static void main(String[] args) {
		int fib1 = 0;
		int fib2 = 1;


		for(int i = 1; i <= 15; i++) {
        	    	int temp= fib1;
       		     	fib1 += fib2;
       		     	fib2 = temp;
            		System.out.println(i + ": " + fib2);
        	}

	}
}

This can help you to make your own logic for your desired assignment.
In this program it print 15fibnoacci numbers with the help of for loop.I have taken fib1=0 and fib2=1.when loop start i have taken another variable temp and assign fib2 value to it which is zero so temp=0.now fib1 += fib2 where as fib2=1 and fib1=0 so fib1=1.In third statement fib2 = temp where temp=0 as we did early. so fib2=0.so first first Fibonacci number is 0 in this way 15 Fibonacci numbers are printed.

[flyingcurry]

class FibTest {
	public static void main(String[] args) {
		int fib1 = 0;
		int fib2 = 1;


		for(int i = 1; i <= 15; i++) {
        	    	int temp= fib1;
       		     	fib1 += fib2;
       		     	fib2 = temp;
            		System.out.println(i + ": " + fib2);
        	}

	}
}

I used this logic to write my own code, it works out perfectly. :)But I am still a bit confused about how the process of changing these variables fib 1, fib 2, and temp work.
Also, what's the difference between this and the recursion method?

Thanks.

[flyingcurry]

And remember, you can't recurse without cursing first.

If you're not familiar with recursion, it'll seem weird at first, but really it's just another method call, only your method calls itself.

Try doing it with recursion.

So the method Extremer showed me is Iteration, I think. But I think our teacher wants us to do recursion. I looked on the web, and there are a lot of similar Fibonacci programs.
Like this

public class Fibonacci {
    public static long fib(int n) {
        if (n <= 1) return n;
        else return fib(n-1) + fib(n-2);
    }

    public static void main(String[] args) {
        int N = Integer.parseInt(args[0]);
        for (int i = 1; i <= N; i++)
            System.out.println(i + ": " + fib(i));
    }

}

But, I do not get the step where "else return fib(n-1) + fib(n-2);"
Is fib a method that automatically does the fibonacci calculation? How are they getting fib(n-1)+fib(n-2) right away without any loops to calculate the previous numbers before the nth fib?

[extemer]

recurrsion is more time consuming than this method and what part are you confuse about in fib1,fib2,temp var can you explain me more

[flyingcurry]

recurrsion is more time consuming than this method and what part are you confuse about in fib1,fib2,temp var can you explain me more

Alright, I think I am getting it, so fib1 is always setting its new value to fib1+fib2, while fib2 takes the value of temp (which is the previous fib1 value), and in the next round of the loop the temp takes the value of the fib 1(from the previous fib1+fib2) and so on.

Thanks!!

[extemer]

How are they getting fib(n-1)+fib(n-2) right away without any loops to calculate the previous numbers before the nth fib?

if you look carefully than you will notice that its the loop through which you are getting the fib number because in loop "System.out.println(i + ": " + fib(i))" method calls "fib(i)" where "fib" is the method which you declared above and "i" is used to print nummeric values e.g 0,1,1,2 etc so as loop circles fib(i) calls the method which calculates your fib number.hope you get my point.

[extemer]

so if you think your problem is solved please don't forget to mark it solved.regards

[jon.kiparsky]

Alright, I think I am getting it, so fib1 is always setting its new value to fib1+fib2, while fib2 takes the value of temp (which is the previous fib1 value), and in the next round of the loop the temp takes the value of the fib 1(from the previous fib1+fib2) and so on.

Thanks!!

One way to think of the thing is a sort of bureacratic process. You go to the Office of Needless Paperwork, and you say "I need this Permit To Paint My Fence stamped." The clerk looks at it, and looks in the rulebook, and says "I need to get authorization for this". So he takes it to his manager, and his manager says "I need to get authorization for this. So your clerk is standing at his manager's desk, and the manager goes off to his supervisor to ask for permission to authorize the clerk to stamp your form. And the supervisor, luckily for you, looks in the rule book and finds that he's allowed to grant that permission. So he gives the manager permission to give the clerk authorization to stamp your permit. So the manager gives the clerk permission to stamp the form, and the clerk stamps your form, and you're allowed to paint your fence.
Notice that this could have gone on as long as I had patience to spin it out: the only way it stops is when someone is allowed to return an answer. Then that answer filters back through the stack of calling procedures (bureaucrats, in my example) until finally the calling procedure gets its answer and goes off to do something with it.

Try that image and see if it makes recursion seem a little easier.

Or visually, it's like this:

You ask (clerk)
->clerk ask (manager)
-> manager ask (supervisor)
<- supervisor says yes
<- manager says yes
<- clerk says yes
You get an answer

[coil]

recurrsion is more time consuming than this method and what part are you confuse about in fib1,fib2,temp var can you explain me more

Recursion may be not as efficient as iteration in certain circumstances, but oftentimes it makes for more readable code. It's also a good concept to learn and understand.
)
@OP: Basically, the calls stack up. If you call fib(4), then your method makes two calls, fib(3) + fib(2). fib(3) makes two calls, fib(2)+fib(1). Since you've defined fib(2) and fib(1) to return 1, you basically get (1+1) + 1=3, which is the 4th fibonacci number.