What is the Fibonacci Sequence?<\/h2>\n\n\n\n
The Fibonacci sequence is a series where each number equals the sum of the two numbers before it:<\/p>\n\n\n\n
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55...<\/p>\n\n\n Here's how it works:<\/p>\n\n\n\n The math formula is: F(n) = F(n-1) + F(n-2)<\/p>\n\n\n\n \n Python Fundamentals for Beginners Free Course<\/a>\n <\/p>\n Master Python basics, from variables to data structures and control flow. Solve real-time problems and build practical skills using Jupyter Notebook.<\/p>\n This is usually what you want to use:<\/p>\n\n\n Why this is good:<\/p>\n\n\n\n Recursion<\/a>\u00a0is when a function calls itself. The recursive solution matches the Fibonacci mathematical formula.<\/p>\n\n\n The problem: This is extremely slow for big numbers because it recalculates the same values over and over. Try fibonacci_recursive(40) and watch it take forever.<\/p>\n\n\n\n If you want recursion that's actually fast, use memoization:<\/p>\n\n\n Or use Python's built-in cache:<\/p>\n\n\n Want the first N Fibonacci numbers as a list?<\/p>\n\n\n![\"Fibonacci](\"http:\/\/www.mygreatlearning.com\/blog\/wp-content\/uploads\/2022\/06\/fibonacci-series-1756379835270.webp\")
<\/figure>\n\n\n\n\n
Method 1: Simple Loop (Best Choice)<\/h2>\n\n\n\n
\npython\ndef fibonacci(n):\n if n <= 1:\n return n\n \n # Start with first two numbers\n prev, curr = 0, 1\n \n # Calculate each number once\n for i in range(2, n + 1):\n prev, curr = curr, prev + curr\n \n return curr\n\n# Test it\nprint(fibonacci(10)) # Output: 55\nprint(fibonacci(0)) # Output: 0\nprint(fibonacci(1)) # Output: 1\n\n<\/pre><\/div>\n\n\n
\n
Method 2: Recursion (Looks Nice, But Slow)<\/h2>\n\n\n\n
\npython\ndef fibonacci_recursive(n):\n if n <= 1:\n return n\n return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)\n\nprint(fibonacci_recursive(10)) # Output: 55\n\n<\/pre><\/div>\n\n\n
Method 3: Smart Recursion with Memory<\/h2>\n\n\n\n
\npython\ndef fibonacci_memo(n, memo={}):\n if n in memo:\n return memo[n]\n \n if n <= 1:\n return n\n \n result = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)\n memo[n] = result\n return result\n\nprint(fibonacci_memo(50)) # Fast now!\n\n<\/pre><\/div>\n\n\n\npython\nfrom functools import lru_cache\n\n@lru_cache(maxsize=None)\ndef fibonacci_cached(n):\n if n <= 1:\n return n\n return fibonacci_cached(n-1) + fibonacci_cached(n-2)\n\nprint(fibonacci_cached(100)) # Very fast\n\n<\/pre><\/div>\n\n\n
Getting Multiple Fibonacci Numbers<\/h2>\n\n\n\n
\npython\ndef fibonacci_sequence(n):\n if n <= 0:\n return []\n if n == 1:\n return [0]\n \n sequence = [0, 1]\n for i in range(2, n):\n next_num = sequence[i-1] + sequence[i-2]\n sequence.append(next_num)\n \n return sequence\n\nprint(fibonacci_sequence(10))\n# Output: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]\n\n<\/pre><\/div>\n\n\n
Performance Comparison<\/h2>\n\n\n\n