Given an integer N. The task is to find the first N Fibonacci numbers.
Examples :
Input: n = 3
Output: 0 1 1Input: n = 7
Output: 0 1 1 2 3 5 8
Program to print first ‘n’ Fibonacci Numbers using recursion:
Below is the idea to solve the problem:
Use recursion to find nth fibonacci number by calling for n-1 and n-2 and adding their return value. The base case will be if n=0 or n=1 then the fibonacci number will be 0 and 1 respectively.
Follow the below steps to Implement the idea:
- Build a recursive function that takes integer N as a parameter.
- If N = 0 fibonacci number will be 0.
- Else if n = 1 Fibonacci number will be 1.
- Else return value for func(n-1) + func(n-2).
Below is the Implementation of the above approach:
C++
#include <iostream> using namespace std; int fibonacci_numbers(int n) { if(n == 0){ return 0; } else if(n == 1){ return 1; } else{ return fibonacci_numbers(n-2) + fibonacci_numbers(n-1); } } int main() { int n = 7; for(int i = 0; i < n; i++) { cout << fibonacci_numbers(i) << " "; } return 0; } // This code is contributed by Rupesh Kapse |
Java
/*package whatever //do not write package name here */import java.io.*; class GFG { public static int fibonacci_numbers(int n) { if(n == 0){ return 0; } else if(n == 1){ return 1; } else{ return fibonacci_numbers(n-2) + fibonacci_numbers(n-1); } } public static void main (String[] args) { int n = 7; for(int i = 0; i < n; i++){ System.out.print(fibonacci_numbers(i)+ " "); } } } // This code is contributed by Rupesh Kapse |
Python3
# python code to print first n fibonacci numbers def fibonacci_numbers(num): if num == 0: return 0 elif num == 1: return 1 else: # printing fibonacci numbers return fibonacci_numbers(num-2)+fibonacci_numbers(num-1) n = 7for i in range(0, n): print(fibonacci_numbers(i), end=" ") # this code is contributed by gangarajula laxmi |
C#
// C# code to implement the approach using System; class GFG { // Method to calculate the nth fibonacci number public static int fibonacci_numbers(int n) { if(n == 0){ return 0; } else if(n == 1){ return 1; } else{ return fibonacci_numbers(n-2) + fibonacci_numbers(n-1); } } // Driver Code public static void Main (string[] args) { int n = 7; for(int i = 0; i < n; i++){ // Function call Console.Write(fibonacci_numbers(i)+ " "); } } } // This code is contributed by phasing17 |
PHP
<?php function fibonacci_numbers($num) { if($num == 0){ return 0; } elseif($num == 1){ return 1; } else{ return (fibonacci_numbers($num-2)+fibonacci_numbers($num-1)); } } $num=7; for ($i = 0; $i < $num; $i++){ echo fibonacci_numbers($i); echo " "; } // This code is contributed by laxmigangarajula03 ?> |
Javascript
<script> // JavaScript code for the above approach function fibonacci_numbers(n) { if (n == 0) { return 0; } else if (n == 1) { return 1; } else { return fibonacci_numbers(n - 2) + fibonacci_numbers(n - 1); } } let n = 7; for (let i = 0; i < n; i++) { document.write(fibonacci_numbers(i) + " "); } // This code is contributed by Potta Lokesh </script> |
Output
0 1 1 2 3 5 8
Time Complexity: O(n*2n)
Auxiliary Space: O(n), For recursion call stack.
An iterative approach to print first ‘n’ Fibonacci numbers:
Below is the idea to solve the problem
- Use two variables f1 and f2 and initialize with 0 and 1 respectively because the 1st and 2nd elements of the Fibonacci series are 0 and 1 respectively.
- Iterate from 1 to n-1 and print f2 then store f2 in temp variable and update f2 with f2 + f1 and f1 as f2.
Below is the Implementation of the above approach:
C++
// C++ program to print // first n Fibonacci numbers #include <bits/stdc++.h> using namespace std; // Function to print // first n Fibonacci Numbers void printFibonacciNumbers(int n) { int f1 = 0, f2 = 1, i; if (n < 1) return; cout << f1 << " "; for (i = 1; i < n; i++) { cout << f2 << " "; int next = f1 + f2; f1 = f2; f2 = next; } } // Driver Code int main() { printFibonacciNumbers(7); return 0; } // This code is contributed by rathbhupendra |
C
// C program to print // first n Fibonacci numbers #include <stdio.h> // Function to print // first n Fibonacci Numbers void printFibonacciNumbers(int n) { int f1 = 0, f2 = 1, i; if (n < 1) return; printf("%d ", f1); for (i = 1; i < n; i++) { printf("%d ", f2); int next = f1 + f2; f1 = f2; f2 = next; } } // Driver Code int main() { printFibonacciNumbers(7); return 0; } |
Java
// Java program to print // first n Fibonacci Numbers class Test { // Method to print // first n Fibonacci Numbers static void printFibonacciNumbers(int n) { int f1 = 0, f2 = 1, i; System.out.print(f1 + " "); if (n < 1) return; for (i = 1; i < n; i++) { System.out.print(f2 + " "); int next = f1 + f2; f1 = f2; f2 = next; } } // Driver Code public static void main(String[] args) { printFibonacciNumbers(7); } } |
Python3
# Python program to print first n # Fibonacci numbers # Function to print first n # Fibonacci Numbers def printFibonacciNumbers(n): f1 = 0 f2 = 1 if (n < 1): return print(f1, end=" ") for x in range(1, n): print(f2, end=" ") next = f1 + f2 f1 = f2 f2 = next # Driven code printFibonacciNumbers(7) # This code is contributed by Danish Raza |
C#
// C# program to print // first n Fibonacci Numbers using System; class Test { // Method to print // first n Fibonacci Numbers static void printFibonacciNumbers(int n) { int f1 = 0, f2 = 1, i; if (n < 1) return; Console.Write(f1 + " "); for (i = 1; i < n; i++) { Console.Write(f2 + " "); int next = f1 + f2; f1 = f2; f2 = next; } } // Driver Code public static void Main() { printFibonacciNumbers(7); } } // This code is contributed by nitin mittal. |
PHP
<?php // PHP program to print first // n Fibonacci numbers // Function to print first n // Fibonacci Numbers function printFibonacciNumbers($n) { $f1 = 0; $f2 = 1; $i; if ($n < 1) return; echo($f1); echo(" "); for ($i = 1; $i < $n; $i++) { echo($f2); echo(" "); $next = $f1 + $f2; $f1 = $f2; $f2 = $next; } } // Driver Code printFibonacciNumbers(7); // This code is contributed by nitin mittal ?> |
Javascript
<script> // Javascript program to print // first n Fibonacci numbers // Function to print // first n Fibonacci Numbers function printFibonacciNumbers(n) { let f1 = 0, f2 = 1, i; if (n < 1) return; document.write(f1 + " "); for (i = 1; i < n; i++) { document.write(f2 + " "); let next = f1 + f2; f1 = f2; f2 = next; } } // Driver Code printFibonacciNumbers(7); // This code is contributed by Mayank Tyagi </script> |
Output
0 1 1 2 3 5 8
Time Complexity: O(n)
Auxiliary Space: O(1)
If you like neveropen and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
