## Generating Fibonacci number in java

This article goes through different implementations of Fibonacci numbers in java.

Brute Force: Recursive

The following code is recursive implementation with time complexity O(2**N). That is time complexity is equal to 2 power N.

```
public int fib(int n) {
if (n == 0)
return 0;
else if (n == 1)
return 1;
else
return fib(n - 1) + fib(n - 2);
}
```

Topdown Implementation

Top-down implementation with time complexity of O(N). Here we cache the value at a specific stage and then see if the stage is already calculated, then return from the cache.

```
public static int fib_topdown(int n, int td[]) {
if (td[n] != 0 && n != 0)
return td[n];
else if (n == 0)
td[n] = 0;
else if (n == 1)
td[n] = 1;
else
td[n] = fib_topdown(n - 1, td) + fib_topdown(n - 2, td);
return td[n];
}
```

Bottom-Up approach

The code is self-explanatory we use the fundamentals of Fibonacci.

```
public static int fib_bottomup(int n) {
if (n < 2)
return n;
int f0 = 0;
int f1 = 1;
int f2 = 0;
for (int i = 2; i <= n; i++) {
f2 = f0 + f1;
f0 = f1;
f1 = f2;
}
return f2;
}
```

Git tags

ReplyDelete