What's the Fibonacci Sequence?<\/h2>\n\n\n\n
It's just adding the previous two numbers:<\/p>\n\n\n\n
0, 1, 1, 2, 3, 5, 8, 13, 21, 34...<\/p>\n\n\n Start with 0 and 1. Then:<\/p>\n\n\n\n Keep going. The math rule is F(n) = F(n-1) + F(n-2).<\/p>\n\n\n\n \n C Programming Course: Master C with Hands-on Projects<\/a>\n <\/p>\n Join our C Programming Course and learn C syntax, operators, expressions, control flow, functions, pointers, structures, file handling, memory management, and modular programming. Build real-world skills through practical projects!<\/p>\n This is what you want 95% of the time. You initialize the first two numbers, then loop to calculate the rest.<\/p>\n\n\n Why this works:<\/p>\n\n\n\n Note:<\/strong> We use This matches the math formula but has a big problem:<\/p>\n\n\n The problem: Try This is O(2^n) time complexity - exponentially slow. Don't use this for anything real.<\/p>\n\n\n\n If you want recursion that actually works, store your results:<\/p>\n\n\n This fixes the recursion by remembering previous results. Now it's O(n) instead of O(2^n).<\/p>\n\n\n\n Sometimes you just want the nth Fibonacci number:<\/p>\n\n\n I tested these on my computer with n=40:<\/p>\n\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
\n\n#include <stdio.h>\n\nvoid printFibonacci(int n) {\n long long first = 0, second = 1, next;\n \n if (n >= 1) {\n printf("Fibonacci Series: ");\n printf("%lld ", first);\n }\n if (n >= 2) {\n printf("%lld ", second);\n }\n \n for (int i = 3; i <= n; i++) {\n next = first + second;\n printf("%lld ", next);\n first = second;\n second = next;\n }\n printf("\\n");\n}\n\nint main() {\n int terms;\n printf("How many Fibonacci numbers? ");\n scanf("%d", &terms);\n \n if (terms <= 0) {\n printf("Please enter a positive number.\\n");\n return 1;\n }\n \n printFibonacci(terms);\n return 0;\n}\n\n<\/pre><\/div>\n\n\n\n
long long<\/code> instead of int<\/code> because Fibonacci numbers get huge fast. Regular int<\/code> overflows around the 47th number.<\/p>\n\n\n\nMethod 2: Recursion (Looks Nice, Runs Terrible)<\/h2>\n\n\n\n
\n\n#include <stdio.h>\n\nlong long fibonacci(int n) {\n if (n <= 1) {\n return n;\n }\n return fibonacci(n-1) + fibonacci(n-2);\n}\n\nint main() {\n int terms;\n printf("How many terms? ");\n scanf("%d", &terms);\n \n printf("Fibonacci Series: ");\n for (int i = 0; i < terms; i++) {\n printf("%lld ", fibonacci(i));\n }\n printf("\\n");\n \n return 0;\n}\n\n<\/pre><\/div>\n\n\nfibonacci(40)<\/code>. It'll take minutes because it recalculates everything repeatedly. fibonacci(3)<\/code> gets calculated dozens of times just to find fibonacci(10)<\/code>.<\/p>\n\n\n\nMethod 3: Smart Recursion with Memory<\/h2>\n\n\n\n
\n\n#include <stdio.h>\n\nlong long memo[100] = {0}; \/\/ Global array, initialized to zeros\n\nlong long fibonacci_memo(int n) {\n if (n <= 1) {\n return n;\n }\n \n \/\/ Already calculated? Return stored result\n if (memo[n] != 0) {\n return memo[n];\n }\n \n \/\/ Calculate and store\n memo[n] = fibonacci_memo(n-1) + fibonacci_memo(n-2);\n return memo[n];\n}\n\nint main() {\n int terms;\n printf("How many terms (max 92)? ");\n scanf("%d", &terms);\n \n printf("Fibonacci Series: ");\n for (int i = 0; i < terms; i++) {\n printf("%lld ", fibonacci_memo(i));\n }\n printf("\\n");\n \n return 0;\n}\n\n<\/pre><\/div>\n\n\nMethod 4: Return Single Number<\/h2>\n\n\n\n
\n\n#include <stdio.h>\n\nlong long fibonacci_single(int n) {\n if (n <= 1) {\n return n;\n }\n \n long long prev = 0, curr = 1, temp;\n \n for (int i = 2; i <= n; i++) {\n temp = prev + curr;\n prev = curr;\n curr = temp;\n }\n \n return curr;\n}\n\nint main() {\n int n;\n printf("Which Fibonacci number do you want? ");\n scanf("%d", &n);\n \n if (n < 0) {\n printf("Please enter a non-negative number.\\n");\n return 1;\n }\n \n printf("F(%d) = %lld\\n", n, fibonacci_single(n));\n return 0;\n}\n\n<\/pre><\/div>\n\n\nPerformance Comparison<\/h2>\n\n\n\n