Fibonacci series is a special kind of series in which the next term is equal to the sum of the previous two terms. Thus, the initial two numbers of the series are always given to us.<\/p>\n
For example, let F0 and F1 denote the first two terms of the Fibonacci series. Then, let F0 = 0 and F1 = 1.
\nSuppose we wish to calculate 10 terms of this Fibonacci series. Then, the series will be:
\nF10 = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55.<\/p>\n
There are various algorithms or methods by which we can find the Fibonacci series for a given set of terms. The most common methods are:<\/p>\n
1. Using recursion<\/p>\n
2. Without using recursion or using Dynamic programming<\/p>\n
3. Space optimized method in DP<\/p>\n
Let us see their implementations one by one.<\/p>\n
The iterative approach is the dynamic programming approach. It makes use of a loop to perform the addition of the previous two terms. The algorithm for the iterative approach will be:<\/p>\n
Procedure Iterative_Fibonacci(n):\n int f0, f1, fib\n f0 = 0\n f1 = 1\n display f0, f1\n for int i := 1 to n:\n fib := f0 + f1 \n f0 := f1\n f1 := fib\n display fib\n END for loop\nEND Iterative_Fibonacci\n<\/pre>\nAlgorithm for Recursive Fibonacci Series:<\/h3>\n
We can also use recursion to generate the Fibonacci series. The pseudo-code for the recursive method is:<\/p>\n
Procedure Recursive_Fibonacci(n)\n int f0, f1\n f0 := 0\n f1 := 1\n if(n <= 1):\n return n\n return Recursive_Fibonacci(n-1) + Recursive_Fibonacci(n-2)\nEND Recursive_Fibonacci\n<\/pre>\nImplementation Using DP(Iterative Approach):<\/h3>\n
Implementation of Fibonacci Series in C:<\/h4>\n
int Iterative_fib(int n)\n{\n int fib[n+2]; \n fib[0] = 0;\n fib[1] = 1;\n for (int i = 2; i <= n; i++)\n fib[i] = fib[i-1] + fib[i-2];\n return fib[n];\n}\n\nint main ()\n{\n int n = 9;\n printf(\"%d\", Iterative_fib(n));\n return 0;\n}\n<\/pre>\nFibonacci series Implementation in C++:<\/h4>\n
#include<bits\/stdc++.h>\n\nint Iterative_fib(int n)\n{\n int fib[n+2]; \n fib[0] = 0;\n fib[1] = 1;\n for (int i = 2; i <= n; i++)\n fib[i] = fib[i-1] + fib[i-2];\n return fib[n];\n}\n\nint main ()\n{\n int n = 9;\n cout<< Iterative_fib(n);\n return 0;\n}\n<\/pre>\nImplementation of Fibonacci Series in Java:<\/h4>\n
class Fibonacci\n{\n static int Iterative_fib(int n)\n {\n int fib[] = new int[n+2]; \n fib[0] = 0;\n fib[1] = 1;\n \n for (int i = 2; i <= n; i++)\n fib[i] = fib[i-1] + fib[i-2];\n return fib[n];\n }\n \n public static void main (String args[])\n {\n int n = 10;\n System.out.println(Iterative_fib(n));\n }\n}\n<\/pre>\nFibonacci series Implementation in Python:<\/h4>\n
def Iterative_fib(n):\n fib = [0, 1]\n for i in range(2, n+1):\n f.append(fib[i-1] + fib[i-2])\n return fib[n]\n \nprint(Iterative_fib(10))\n<\/pre>\nImplementation Using Space Optimization in DP:<\/h3>\n
Implementation of Fibonacci series in C:<\/h4>\n
#include<stdio.h>\nint SO_fib(int n)\n{\n int num1 = 0, num2 = 1, num3;\n if( n == 0)\n return num1;\n for (int i = 2; i <= n; i++)\n {\n num3 = num1 + num2;\n num1 = num2;\n num2 = num3;\n }\n return num2;\n}\n\nint main ()\n{\n int n = 10;\n printf(\"%d\", SO_fib(n));\n return 0;\n}\n<\/pre>\nFibonacci series Implementation in C++:<\/h4>\n
#include<bits\/stdc++.h>\nint SO_fib(int n)\n{\n int num1 = 0, num2 = 1, num3;\n if( n == 0)\n return num1;\n for (int i = 2; i <= n; i++)\n {\n num3 = num1 + num2;\n num1 = num2;\n num2 = num3;\n }\n return num2;\n}\n\nint main ()\n{\n int n = 10;\n cout << SO_fib(n));\n return 0;\n}\n<\/pre>\nImplementation of Fibonacci series in Java:<\/h4>\n
class Fibonacci\n{\n static int SO_fib(int n)\n {\n int num1 = 0, num2 = 1, num3;\n if (n == 0)\n return num1;\n for (int i = 2; i <= n; i++)\n {\n num3 = num1 + num2;\n num1 = num2;\n num2 = num3;\n }\n return num2;\n }\n\n public static void main (String args[])\n {\n int n = 10;\n System.out.println(SO_fib(n));\n }\n}\n<\/pre>\nFibonacci series Implementation in Python:<\/h4>\n
def SO_fib(n):\n num1 = 0\n num2 = 1\n if n < 0:\n print(\"Incorrect input\")\n elif n == 0:\n return num1\n elif n == 1:\n return num2\n else:\n for i in range(2, n+1):\n num3 = num1 + num2\n num1 = num2\n num2 = num3\n return num2\n\nprint(SO_fib(10))\n<\/pre>\nImplementation Using Recursion:<\/h3>\n
Implementation of Fibonacci series in C:<\/h4>\n
#include<stdio.h>\nint Recursive_fib(int n)\n{\n if (n <= 1)\n return n;\n return Recursive_fib(n-1) + Recursive_fib(n-2);\n}\n\nint main ()\n{\n int n = 10;\n printf(\"%d\", Recursive_fib(n));\n return 0;\n}\n<\/pre>\nFibonacci series Implementation in C++:<\/h4>\n
#include<bits\/stdc++.h>\nint Recursive_fib(int n)\n{\n if (n <= 1)\n return n;\n return Recursive_fib(n-1) + Recursive_fib(n-2);\n}\n\nint main ()\n{\n int n = 10;\n cout << Recursive_fib(n);\n return 0;\n}\n<\/pre>\nImplementation of Fibonacci Series in Java:<\/h4>\n
class Fibonacci\n{\n static int Recursive_fib(int n)\n {\n if (n <= 1)\n return n;\n return Recursive_fib(n-1) + Recursive_fib(n-2);\n }\n \n public static void main (String args[])\n {\n int n = 9;\n System.out.println(Recursive_fib(n));\n }\n}\n<\/pre>\nFibonacci series Implementation in Python:<\/h4>\n
def Recursive_fib(n):\n if n<0:\n print(\"Incorrect input\")\n elif n==0:\n return 0\n elif n==1:\n return 1\n else:\n return Recursive_fib(n-1) + Recursive_fib(n-2)\n\nprint(Recursive_fib(10))\n<\/pre>\nComplexity Analysis of Fibonacci series:<\/h3>\n
Different methods generate different complexities for the same problem. These complexities are:<\/p>\n
| Method<\/b><\/td>\n | Time complexity<\/b><\/td>\n | Space complexity<\/b><\/td>\n<\/tr>\n| Using recursion<\/span><\/td>\n | T(n) = T(n-1) + T(n-2)<\/span><\/td>\n | O(n)<\/span><\/td>\n<\/tr>\n | Using DP<\/span><\/td>\n | O(n)<\/span><\/td>\n | O(1)<\/span><\/td>\n<\/tr>\n | Space optimization of DP<\/span><\/td>\n | O(n)<\/span><\/td>\n | O(1)<\/span><\/td>\n<\/tr>\n | Using the power of matrix method<\/span><\/td>\n | O(n)<\/span><\/td>\n | O(1)<\/span><\/td>\n<\/tr>\n | Optimized matrix method<\/span><\/td>\n | O(log n)<\/span><\/td>\n | O(log n)<\/span><\/td>\n<\/tr>\n | Recursive method in O(log n) time<\/span><\/td>\n | O(log n)<\/span><\/td>\n | O(n)<\/span><\/td>\n<\/tr>\n | Using direct formula<\/span><\/td>\n | O(log n)<\/span><\/td>\n | O(1)<\/span><\/td>\n<\/tr>\n | DP using memoization<\/span><\/td>\n | O(n)<\/span><\/td>\n | O(1)<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n | Conclusion:<\/h3>\nIn this article, we have defined the Fibonacci series. We have also seen various methods with which we can implement it. We have implemented these methods in C, C++, Java and Python.<\/p>\n","protected":false},"excerpt":{"rendered":" Fibonacci series is a special kind of series in which the next term is equal to the sum of the previous two terms. Thus, the initial two numbers of the series are always given...<\/p>\n","protected":false},"author":1,"featured_media":84163,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3555],"tags":[4088,4089,4090],"class_list":["post-83705","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structure","tag-fibonacci-series","tag-fibonacci-series-algorithm","tag-fibonacci-series-implementation"],"yoast_head":"\n |