#Algorithm: Generate Fibonacci In Java

Also Check: Algorithms and System Design Interview Questions

Generate the Fibonacci recursively and iteratively in Java
In fibonacci series, next number is the sum of previous two numbers for example 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 etc. The first two numbers of fibonacci series are 0 and 1.

There are two ways to generate the fibonacci series: With iteration and with recursion.

	public void iterativeFibonacci() {
	int n1 = 0, n2 = 1;
	int n3, i, count = 10;
	// printing 0 and 1
	System.out.print(n1 + " " + n2);
	//loop starts from 2 because 0
	//and 1 are already printed
	for (i = 2; i < count; ++i)
	{
	n3 = n1 + n2;
	System.out.print(" " + n3);
	n1 = n2;
	n2 = n3
	}
	}
	static int n1 = 0, n2 = 1, n3 = 0;
	static void recursiveFibonacci(int count) {
	if (count > 0) {
	n3 = n1 + n2;
	n1 = n2;
	n2 = n3;
	System.out.print(" " + n3);
	recursiveFibonacci(count - 1);
	}
	}
	//using fork join pool
	class MyFibonacci extends
	RecursiveTask<Integer>{
	final int n;
	MyFibonacci(int n){
	this.n=n;
	}
	@Override
	protected Integer compute() {
	if(n<=1) return n;
	MyFibonacci f1=new MyFibonacci(n-1);
	f1.fork();
	MyFibonacci f2=new MyFibonacci(n-2);
	f2.fork();
	return f1.join()+f2.join();
	}
	}

view raw Fibonacci.java hosted with ❤ by GitHub

Time and Space Complexity Of Recursive and Iterative approach
The time complexity of the iterative code is linear, as the loop runs from 2 to n, i.e. it runs in O(n) time. The time taken by recursive Fibonacci is O(2^n) or exponential.

For the iterative approach, the amount of space required is the same for fib(6) and fib(100), i.e. as N changes the space/memory used remains the same. Hence it’s space complexity is O(1) or constant. The space complexity of Fibonacci recursive is O(N).