Given a number N, we need to find the Fibonacci Series up to the N term.

The Fibonacci sequence is a series of elements in which the first two elements are added to get the next element, starting from 0 and 1.

Examples:

Input: N = 10 
Output: 0 1 1 2 3 5 8 13 21 34 
Here first term of Fibonacci is 0 and second is 1, so that 3rd term = first(o) + second(1) etc and so on.

Input: N = 15 
Output: 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377  

Method 1 – Iterative:

Initialize the first and second numbers to 0 and 1. Next, we print the first and second numbers. Then we send the process to an iterative while loop, where we get the next number by adding the first two numbers and simultaneously swapping the first number and the second number, and the second number and the third number.

The implementation of the former method is as follows:

// Java program for the above approach

class GFG {

	// Function to print N Fibonacci Number
	static void Fibonacci(int N)
	{
		int num1 = 0, num2 = 1;

		int counter = 0;

		// Iterate till counter is N
		while (counter < N) {

			// Print the number
			System.out.print(num1 + " ");

			// Swap
			int num3 = num2 + num1;
			num1 = num2;
			num2 = num3;
			counter = counter + 1;
		}
	}

	// Driver Code
	public static void main(String args[])
	{
		// Given Number N
		int N = 10;

		// Function Call
		Fibonacci(N);
	}
}

Output:

0 1 1 2 3 5 8 13 21 34

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

Method 2 – Using Recursion:

Since Fibonacci Number is the summation of the two previous numbers. We can use recursion as per the following condition:

1. Get the number whose Fibonacci series needs to be calculated.
2. Recursively iterate from value N to 1:
   • Base case: If the value called recursively is less than 1, the return 1 the function.
   • Recursive call: If the base case is not met, then recursively call for previous two value as:

recursive_function(N – 1) + recursive_function(N – 2);

• Return statement:  On each recursive call (except for the basic case), the recursive function that returns the above two values ??is:

// Recursive implementation of
// Fibonacci Series

class GFG {

	// Function to print the fibonacci series
	static int fib(int n)
	{
		// Base Case
		if (n <= 1)
			return n;

		// Recursive call
		return fib(n - 1)
			+ fib(n - 2);
	}

	// Driver Code
	public static void
	main(String args[])
	{
		// Given Number N
		int N = 10;

		// Print the first N numbers
		for (int i = 0; i < N; i++) {

			System.out.print(fib(i) + " ");
		}
	}
}

Output:

0 1 1 2 3 5 8 13 21 34

Time Complexity: O(2^N)  
Auxiliary Space: O(1)

Method 3 – Using Dynamic Programming:

 We can avoid the duplication of work done in Method 2 by storing the Fibonacci numbers calculated so far. Here are the steps:

1. Create an array arr[] of size N.
2. Initialize arr[0] = 0, arr[1] = 1.
3. Iterate over [2, N] and update the array arr[] as:

arr[i] = arr[i – 2] + arr[i – 1]

4. Print the value of arr[N].

Below is the implementation of the above approach:

// Dynamic Programming approach for
// Fibonacci Series

class fibonacci {

	// Function to find the fibonacci Series
	static int fib(int n)
	{

		// Declare an array to store
		// Fibonacci numbers.
		// 1 extra to handle case, n = 0
		int f[] = new int[n + 2];

		int i;

		// 0th and 1st number of
		// the series are 0 and 1
		f[0] = 0;
		f[1] = 1;

		for (i = 2; i <= n; i++) {

			// Add the previous 2 numbers
			// in the series and store it
			f[i] = f[i - 1] + f[i - 2];
		}

		// Nth Fibonacci Number
		return f[n];
	}

	public static void
	main(String args[])
	{
		// Given Number N
		int N = 10;

		// Print first 10 term
		for (int i = 0; i < N; i++)
			System.out.print(fib(i) + " ");
	}
}

Output:

0 1 1 2 3 5 8 13 21 34

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