# Program to find N-th Fibonacci Number in Java

## N-th Fibonacci Number in Java

Here, in this page we will discuss the program to find N-th Fibonacci Number in Java. he sequence F(n) of Fibonacci numbers is defined by the recurrence relation, F(n) = F(n-1) + F(n-2) where, F(0) = 0 and F(1) = 1.

In this page we will discuss the different methods to solve this problem in optimized way. ## Method 1 (Using Recursion) :

• Create a function fib(int n),
• Inside that function define the base condition, which is if(n<=1) return n,
• Otherwise return fib(n-1)+fib(n-2).

### Time and Space Complexity :

• Time-Complexity : O(n)
• Space-Complexity : O(1) ## Code to find N-th Fibonacci Number in Java

Run
```class Main {
static int fib(int n)
{
if (n <= 1)    //Base Condition
return n;
return fib(n - 1) + fib(n - 2);
}

public static void main(String args[])
{
int n = 4;
System.out.println(fib(n));
}
}```
`Output :3`

## Method 2 (Using DP) :

• Create a function fib(int n),
• Inside that function, declare an array say f[] to store the fibonacci number.
• Set, f=0
• If(n>0):
• Set, f =1.
• Now, run a loop from i=2 to i<=n,
• Set, f[i]=f[i-1]+f[i-2]
• At last, return f[n].

### Time and Space Complexity :

• Time-Complexity : O(n)
• Space-Complexity : O(n) ## Code in Java

Run
```class Main {
static int fib(int n)
{
int f[] = new int[n + 1];
int i;

f = 0;

if (n > 0) {
f = 1;

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

return f[n];
}

public static void main(String args[])
{
int n = 4;
System.out.println(fib(n));
}
}```
`Output :3`

## Method 3 (Using DP with optimized space) :

• Create a function fib(int n),
• Inside that function, declare three variables, a=0, b=1 and c.
• If(n==0), return a.
• Now run a loop from i=2 to i<=n,
• Set, c=a+b, a=b and b=c
• At last, return b.

### Time and Space Complexity :

• Time-Complexity : O(n)
• Space-Complexity : O(1)

## Code in Java

Run
```class Main {
static int fib(int n)
{
int a = 0, b = 1, c;
if (n == 0)
return a;
for (int i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return b;
}

public static void main(String args[])
{
int n = 4;
System.out.println(fib(n));
}
}```
`Output :3`

### 2 comments on “Program to find N-th Fibonacci Number in Java”

• Satendra

Class fact{
public static int calf(int n){
If(n==1|| n==0){
return 1;
}
int n1= calf(n-1);
Int factorial= n*n1;
return factorial;
}
public static void main (String[]args){
Int n=5;
int ans= calf(n);
system.out.printl(calf);
}} 5
• Satendra

System.out.println(ans); 1