Recursion Approach to Find and Print Nth Fibonacci Numbers
In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation: with seed values and and .
The Nth Fibonacci Number can be found using the recurrence relation shown above:
- if n = 0, then return 0.
- If n = 1, then it should return 1.
- For n > 1, it should return Fn-1 + Fn-2
Below is the implementation of the above approach:
C++
// Fibonacci Series using Recursion #include <bits/stdc++.h> using namespace std; int fib( int n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); } int main() { int n = 9; cout << n << "th Fibonacci Number: " << fib(n); return 0; } // This code is contributed // by Akanksha Rai |
C
// Fibonacci Series using Recursion #include <stdio.h> int fib( int n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); } int main() { int n = 9; printf ( "%dth Fibonacci Number: %d" , n, fib(n)); return 0; } |
Java
// Fibonacci Series using Recursion import java.io.*; class fibonacci { static int fib( int n) { if (n <= 1 ) return n; return fib(n - 1 ) + fib(n - 2 ); } public static void main(String args[]) { int n = 9 ; System.out.println( n + "th Fibonacci Number: " + fib(n)); } } /* This code is contributed by Rajat Mishra */ |
Python3
# Fibonacci series using recursion def fibonacci(n): if n < = 1 : return n return fibonacci(n - 1 ) + fibonacci(n - 2 ) if __name__ = = "__main__" : n = 9 print (n, "th Fibonacci Number: " ) print (fibonacci(n)) # This code is contributed by Manan Tyagi. |
C#
// C# program for Fibonacci Series // using Recursion using System; public class GFG { public static int Fib( int n) { if (n <= 1) { return n; } else { return Fib(n - 1) + Fib(n - 2); } } // driver code public static void Main( string [] args) { int n = 9; Console.Write(n + "th Fibonacci Number: " + Fib(n)); } } // This code is contributed by Sam007 |
Javascript
// Javascript program for Fibonacci Series // using Recursion function Fib(n) { if (n <= 1) { return n; } else { return Fib(n - 1) + Fib(n - 2); } } // driver code let n = 9; console.log(n + "th Fibonacci Number: " + Fib(n)); |
PHP
<?php // PHP program for Fibonacci Series // using Recursion function Fib( $n ) { if ( $n <= 1) { return $n ; } else { return Fib( $n - 1) + Fib( $n - 2); } } // driver code $n = 9; echo $n . "th Fibonacci Number: " . Fib( $n ); // This code is contributed by Sam007 ?> |
Output
34
Time Complexity: Exponential, as every function calls two other functions.
Auxiliary space complexity: O(n), as the maximum depth of the recursion tree is n.
Nth Fibonacci Number
Given a number n, print n-th Fibonacci Number.
The Fibonacci numbers are the numbers in the following integer sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ……..
Examples:
Input : n = 1
Output : 1
Input : n = 9
Output : 34
Input : n = 10
Output : 55
C++
// Fibonacci Series using Space Optimized Method #include <bits/stdc++.h> using namespace std; int fib( int n) { int a = 0, b = 1, c, i; if (n == 0) return a; for (i = 2; i <= n; i++) { c = a + b; a = b; b = c; } return b; } // Driver code int main() { int n = 9; cout << fib(n); return 0; } // This code is contributed by Code_Mech |
C
// Fibonacci Series using Space Optimized Method #include <stdio.h> int fib( int n) { int a = 0, b = 1, c, i; if (n == 0) return a; for (i = 2; i <= n; i++) { c = a + b; a = b; b = c; } return b; } int main() { int n = 9; printf ( "%d" , fib(n)); getchar (); return 0; } |
Java
// Java program for Fibonacci Series using Space // Optimized Method public class fibonacci { static int fib( int n) { int a = 0 , b = 1 , c; if (n == 0 ) return a; for ( int i = 2 ; i <= n; i++) { c = a + b; a = b; b = c; } return b; } public static void main(String args[]) { int n = 9 ; System.out.println(fib(n)); } }; // This code is contributed by Mihir Joshi |
Python3
# Function for nth fibonacci number - Space Optimisation # Taking 1st two fibonacci numbers as 0 and 1 def fibonacci(n): a = 0 b = 1 if n < 0 : print ( "Incorrect input" ) elif n = = 0 : return a elif n = = 1 : return b else : for i in range ( 2 , n + 1 ): c = a + b a = b b = c return b # Driver Program print (fibonacci( 9 )) # This code is contributed by Saket Modi |
C#
// C# program for Fibonacci Series // using Space Optimized Method using System; namespace Fib { public class GFG { static int Fib( int n) { int a = 0, b = 1, c = 0; // To return the first Fibonacci number if (n == 0) return a; for ( int i = 2; i <= n; i++) { c = a + b; a = b; b = c; } return b; } // Driver function public static void Main( string [] args) { int n = 9; Console.Write( "{0} " , Fib(n)); } } } // This code is contributed by Sam007. |
Javascript
<script> // Javascript program for Fibonacci Series using Space Optimized Method function fib(n) { let a = 0, b = 1, c, i; if ( n == 0) return a; for (i = 2; i <= n; i++) { c = a + b; a = b; b = c; } return b; } // Driver code let n = 9; document.write(fib(n)); // This code is contributed by Mayank Tyagi </script> |
PHP
<?php // PHP program for Fibonacci Series // using Space Optimized Method function fib( $n ) { $a = 0; $b = 1; $c ; $i ; if ( $n == 0) return $a ; for ( $i = 2; $i <= $n ; $i ++) { $c = $a + $b ; $a = $b ; $b = $c ; } return $b ; } // Driver Code $n = 9; echo fib( $n ); // This code is contributed by anuj_67. ?> |
Output
34
Time Complexity: O(n)
Auxiliary Space: O(1)