Program to print first N term of Fibonacci Series
1. Print Fibonacci series using Recursion:
In this method, we will use a function that prints the first two terms, and the rest of the terms are then handled by the other function that makes use of a recursive technique to print the next terms of the sequence.
Below is the implementation of the above idea:
C++
// C++ Program to print the Fibonacci // series using recursion #include <iostream> using namespace std; // First two values int prev1 = 1; int prev2 = 0; // Recursive function to print the // fibonacci series void fib( int n) { if (n < 3) { return ; } int fn = prev1 + prev2; prev2 = prev1; prev1 = fn; cout << fn << " " ; return fib(n - 1); } // Function that handles the first two terms // and calls the recursive function void printFib( int n) { // When the number of terms is less than 1 if (n < 1) { cout << "Invalid number of terms\n" ; } // When the number of terms is 1 else if (n == 1) { cout << 0; } // When the number of terms is 2 else if (n == 2) { cout << "0 1" ; } // Number of terms greater than 2 else { cout << "0 1 " ; fib(n); } return ; } // Driver code int main() { int n = 9; // Function call printFib(n); return 0; } |
Java
/*package whatever //do not write package name here */ import java.io.*; public class FibonacciSeries { // Recursive function to print the Fibonacci series static void fib( int n, int prev1, int prev2) { if (n < 3 ) { return ; } int fn = prev1 + prev2; prev2 = prev1; prev1 = fn; System.out.print(fn + " " ); fib(n - 1 , prev1, prev2); } // Function that handles the first two terms and calls the recursive function static void printFib( int n) { // When the number of terms is less than 1 if (n < 1 ) { System.out.println( "Invalid number of terms" ); } // When the number of terms is 1 else if (n == 1 ) { System.out.println( 0 ); } // When the number of terms is 2 else if (n == 2 ) { System.out.println( "0 1" ); } // Number of terms greater than 2 else { System.out.print( "0 1 " ); fib(n, 1 , 0 ); } } public static void main(String[] args) { int n = 9 ; // Function call printFib(n); } } // This code is contributed by guptapratik |
Python3
# Recursive function to print the Fibonacci series def fib(n, prev1, prev2): if n < 3 : return fn = prev1 + prev2 prev2 = prev1 prev1 = fn print (fn, end = " " ) fib(n - 1 , prev1, prev2) # Function that handles the first two terms and calls the recursive function def print_fib(n): # When the number of terms is less than 1 if n < 1 : print ( "Invalid number of terms" ) # When the number of terms is 1 elif n = = 1 : print ( 0 ) # When the number of terms is 2 elif n = = 2 : print ( "0 1" ) # Number of terms greater than 2 else : print ( "0 1" , end = " " ) fib(n, 1 , 0 ) # Driver code if __name__ = = "__main__" : n = 9 # Function call print_fib(n) |
C#
using System; class Program { // First two values static int prev1 = 1; static int prev2 = 0; // Recursive function to print the Fibonacci series static void Fib( int n) { if (n < 3) { return ; } int fn = prev1 + prev2; prev2 = prev1; prev1 = fn; Console.Write(fn + " " ); Fib(n - 1); } // Function that handles the first two terms and calls the recursive function static void PrintFib( int n) { // When the number of terms is less than 1 if (n < 1) { Console.WriteLine( "Invalid number of terms" ); } // When the number of terms is 1 else if (n == 1) { Console.WriteLine(0); } // When the number of terms is 2 else if (n == 2) { Console.WriteLine( "0 1" ); } // Number of terms greater than 2 else { Console.Write( "0 1 " ); Fib(n); } } // Driver code static void Main() { int n = 9; // Function call PrintFib(n); } } |
Javascript
// Recursive function to print the Fibonacci series function fib(n, prev1, prev2) { if (n < 3) { return ; } let fn = prev1 + prev2; prev2 = prev1; prev1 = fn; process.stdout.write(fn + " " ); fib(n - 1, prev1, prev2); } // Function that handles the first two terms and calls the recursive function function printFib(n) { // When the number of terms is less than 1 if (n < 1) { console.log( "Invalid number of terms" ); } // When the number of terms is 1 else if (n === 1) { console.log(0); } // When the number of terms is 2 else if (n === 2) { console.log( "0 1" ); } // Number of terms greater than 2 else { process.stdout.write( "0 1 " ); fib(n, 1, 0); } } // Driver code const n = 9; // Function call printFib(n); |
Complexity Analysis:
- Time complexity: O(n), It is because, for printing n terms, the fib() function will call itself recursively for (n – 2) times and each time it will take constant time.
- Auxiliary Space: O(n), It is because, for each recursive call of the fib() function, a separate stack frame is created. For (n-2) calls, (n-2) stack frames are created with results in the O(n) space complexity.
2. Fibonacci series using loops
In this method, we use one of the C loops to iterate and print the current term. The first two terms, F1 and F2 are handled separately. After that, we use two variables to store the previous two terms and keep updating them as we move to print the next term.
Below is the implementation of the above idea:
C++
// C++ Program to print the fibonacci series // using iteration (loops) #include <iostream> using namespace std; // Function to print fibonacci series void printFib( int n) { if (n < 1) { cout << "Invalid Number of terms\n" ; return ; } // When number of terms is greater than 0 int prev1 = 1; int prev2 = 0; // For loop to print fibonacci series for ( int i = 1; i <= n; i++) { if (i > 2) { int num = prev1 + prev2; prev2 = prev1; prev1 = num; cout << num << " " ; } // For first two terms if (i == 1) { cout << prev2 << " " ; } if (i == 2) { cout << prev1 << " " ; } } } // Driver code int main() { int n = 9; // Function Call printFib(n); return 0; } |
Java
public class FibonacciSeries { // Function to print Fibonacci series static void printFib( int n) { if (n < 1 ) { System.out.println( "Invalid Number of terms" ); return ; } // When number of terms is greater than 0 int prev1 = 1 ; int prev2 = 0 ; // For loop to print Fibonacci series for ( int i = 1 ; i <= n; i++) { if (i > 2 ) { int num = prev1 + prev2; prev2 = prev1; prev1 = num; System.out.print(num + " " ); } // For first two terms if (i == 1 ) { System.out.print(prev2 + " " ); } if (i == 2 ) { System.out.print(prev1 + " " ); } } } // Driver code public static void main(String[] args) { int n = 9 ; // Function Call printFib(n); } } |
Python3
def print_fib(n): if n < 1 : print ( "Invalid Number of terms" ) return # When number of terms is greater than 0 prev1 = 1 prev2 = 0 # For loop to print Fibonacci series for i in range ( 1 , n + 1 ): if i > 2 : num = prev1 + prev2 prev2 = prev1 prev1 = num print (num, end = " " ) # For first two terms if i = = 1 : print (prev2, end = " " ) if i = = 2 : print (prev1, end = " " ) # Driver code n = 9 # Function Call print_fib(n) |
C#
using System; class Program { // Function to print Fibonacci series static void PrintFib( int n) { if (n < 1) { Console.WriteLine( "Invalid Number of terms" ); return ; } // When the number of terms is greater than 0 int prev1 = 1; int prev2 = 0; // For loop to print Fibonacci series for ( int i = 1; i <= n; i++) { if (i > 2) { int num = prev1 + prev2; prev2 = prev1; prev1 = num; Console.Write(num + " " ); } // For the first two terms if (i == 1) { Console.Write(prev2 + " " ); } if (i == 2) { Console.Write(prev1 + " " ); } } } // Driver code static void Main( string [] args) { int n = 9; // Number of terms in the Fibonacci series // Function Call PrintFib(n); } } |
Javascript
// Function to print Fibonacci series function printFib(n) { if (n < 1) { console.log( "Invalid Number of terms" ); return ; } // When the number of terms is greater than 0 let prev1 = 1; let prev2 = 0; // For loop to print the Fibonacci series for (let i = 1; i <= n; i++) { if (i > 2) { const num = prev1 + prev2; prev2 = prev1; prev1 = num; console.log(num + " " ); } // For the first two terms if (i === 1) { console.log(prev2 + " " ); } if (i === 2) { console.log(prev1 + " " ); } } console.log(); // Add a newline after printing the series } // Driver code const n = 9; // Function Call printFib(n); |
Complexity Analysis
- Time Complexity: O(n), Because for n number for terms, the loop inside the printFib() function will be executed n times.
- Auxiliary Space: O(1), Because we only used a few variables which don’t depends on the number of terms to be printed
Fibonacci Series
Ever wondered about the cool math behind the Fibonacci series? This simple pattern has a remarkable presence in nature, from the arrangement of leaves on plants to the spirals of seashells. We’re diving into this Fibonacci Series sequence. It’s not just math, it’s in art, nature, and more! Let’s discover the secrets of the Fibonacci series together.