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 = 7 for 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 |
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> |
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 ?> |
0 1 1 2 3 5 8
Time Complexity: O(n*2n)
Auxiliary Space: O(n), For recursion call stack.
Program to print first n Fibonacci Numbers | Set 1
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