CareerCup

public static void fibonacci(int n) {
		int prevNumber = 0;
		int currentNumber = 1;
		while (currentNumber <= n) {
			System.out.println(prevNumber);
			int temp = currentNumber;
			currentNumber = currentNumber + prevNumber;
			prevNumber = temp;
		}
		System.out.println(prevNumber);
	}

int main()
 {
     int n, i;
     printf("Enter the number of elements in the sequence");
     scanf("%d", &n);
     for( i=0 ;i<n;i++)
    {
       printf("%d",fibo(i));
  }
}
int fibo(int n) {
 if ( n == 0)
  return 0;
else if (n ==1)
   return 1;
 else
   return fibo(n-1) + fibo(n-2);
}

def FIBO(f0, f1, n):
    print f0
    while(f1<=n):
        print f1
        f1 = f0 + f1
        f0 = f1-f0

FIBO(0,1,89)

Java Solution:

public static void main(String[] args) {

		System.out.println("Enter the no of elements");
		Scanner sc1 = new Scanner(System.in);
		int n = sc1.nextInt();
		
		System.out.println(displayFibonacci(n).toString());
		
	}
	
	private static StringBuffer displayFibonacci(int n){
		
		StringBuffer buffer = new StringBuffer();
		List<Integer> list = new ArrayList<Integer>();
		
		for(int i=0; i < n; i++){
			if(i == 0){
				list.add(0);
				buffer.append(String.valueOf(0));
			}
			
			if (i == 1 || i == 2){
				
				list.add(1);
				buffer.append(",");
				buffer.append(String.valueOf(1));
			}
			
			if(i > 2){
				list.add(list.get(i-1) + list.get(i-2));
				buffer.append(",");
				buffer.append(list.get(i-1) + list.get(i-2));
			}
		}
		
		return buffer;
	}

Iterative Java Solution O(N), recursive one will take exponential time O(2^n)

public int fibIter(int n){
	  
	  int fn=0, fnMinus1=1, fnMinus2=0;
	 
	  for(int i=2; i<=n; i++){

		  fn=fnMinus1+fnMinus2;
		  fnMinus2=fnMinus1;
		  fnMinus1=fn;
		  System.out.print(fn);
	  }
	  System.out.print(fn);
	  return fn;
  }

import java.util.ArrayList;
import java.util.Scanner;

public class Fibonacci {

public void fib(int size, int firstNum) {
int previous = 0;
int current = firstNum;
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(current);
for(int i = 1 ; i<size ; i++) {
int temp = current;
current = previous + temp;
previous = temp ;
list.add(current);
}
System.out.println("The fibonnaci series is :");
System.out.println(list);
}

public static void main(String [] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("Enter the first element");
int firstNum = scanner.nextInt();

System.out.println("Enter the size of the Fibonacci Series");

int size = scanner.nextInt();
Fibonacci object = new Fibonacci();
object.fib(size,firstNum);
}

}

Dynamic Programming Approach:

Avoid the repeated work done (By recursion method) by storing the Fibonacci numbers calculated so far.
This can even further optimized the space by storing the previous 2 numbers only because that is all we need to get the next Fibonnaci number in series.

int fibo ( int Num ) {
  	int prev1 = 0, prev2 = 1, next ;

  	if( 0 == Num )
    		return prev1 ;

  	for (int i = 2; i <= num;  i++ )  {
     		next = prev1 + prev2 ;
     		prev1 = prev2 ;
     		prev2 = next ;
  	}
  	return prev2;
}

Time Complexity: O(N)
Space Complexity: O(1)

class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		fib(10);
	}
	
	public static void fib(int n)
	{
			
		int p=1,q=1;
		while (p<n)
		{
			System.out.println(p);
			int temp;
			temp = q;
			q = p + q;
			p = temp;
		}
			 
	}

}

Dynamic Programming Would be the best approach