payal-kothari
6/22/2017 - 7:10 AM

## Fibonacci sequence (Rec, iter, dynamic).java

``````Recursive:

public class fibRec {

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

public static void main(String[] args) {
for (int i = 0; i < 4; i++){
System.out.println(Fibonacci(i));
}
}
}

Approach 2:
public class RecursionExample4 {

static int n1=0,n2=1,n3=0;

static void printFibo(int count){

if(count>0){

n3 = n1 + n2;

n1 = n2;

n2 = n3;

System.out.print(" "+n3);

printFibo(count-1);

}

}

public static void main(String[] args) {

int count=15;

System.out.print(n1+" "+n2);//printing 0 and 1

printFibo(count-2);//n-2 because 2 numbers are already printed

}

}

Iterative:

public class fibIter {

static int Fibonacci(int n) {
if (n <= 1) {
return n;
}
int a = 1, b = 1, c;
for (int i = 2; i < n ; ++i) {
c = a + b;
b = a;
a = c;
}
return a;
}

public static void main(String[] args) {
for (int i = 0; i < 4; i++){
System.out.println(Fibonacci(i));
}
}
}

http://algorithms.tutorialhorizon.com/introduction-to-dynamic-
programming- bonacci-series/
(http://algorithms.tutorialhorizon.com/introduction-to-dynamic-
programming- bonacci-series/)

Dynamic Pro gram ming Approaches:
Bottom-Up
Top-Down
Bottom-Up Approach:

Suppose we need to solve the problem for N, We start solving the problem with the smallest possible inputs and store it for
future. Now as you calculate for the bigger values use the stored solutions (solution for smaller problems).

Bottom-Up solution for Fibonacci Series:

public class fibDP {

static public void Fibonacci(int x) {
int fib[] = new int[x + 1];
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i < x + 1; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
for(int j=0; j< x; j++){
System.out.println(fib[j]);
}
}

public static void main(String[] args) {
Fibonacci(4);
}
}

Top-Down Approach:

Break the problem into sub-problems and solve them as needed and store the solution for future.

public int  bTopDown(int n) {
if(n==0) return 1;
if(n==1) return 1;
if( b[n]!=0){
return  b[n];
}else{
b[n] =  bTopDown(n-1) +  bTopDown(n-2);
return  b[n];
}
}

``````