Summary: in this tutorial, you will learn how to develop a C program for Fibonacci series using recursion and iteration techniques.
Introduction to Fibonacci numbers
In mathematics, the Fibonacci numbers, or Fibonacci series, are the numbers that are in the following sequence:
0,1,1,2,3,5,6,13,21,34,55,89,…
The first number in the Fibonacci sequence is 0, the second number is 1. The subsequent number is the result of the sum of the previous two e.g., third number 1 = 1+0, fourth number 2=1+1, fifth number 3 = 2+1, etc.
The Fn number is defined as follows:
Fn = Fn-1 + Fn-2,
with the seed values:
F0 = 0, F1 = 1.
C Programs for Fibonacci Series
C Program for Fibonacci series using recursion
The first simple approach of developing a function that calculate the nth number in the Fibonacci series using a recursive function. The following is Fibonacci series program in c:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | #include <stdio.h> typedef unsigned long long F; F fibonacci(F n); int main() { int n, i, j; printf("--- Fibonacci series program ---\n"); printf("Enter a number:"); scanf("%d",&n); printf("\nFibonacci series:\n"); j = 0; for ( i = 1 ; i <= n ; i++ ) { printf("%d ", fibonacci(j)); j++; } } F fibonacci(F n) { if ( n == 0 ) return 0; if ( n == 1 ) return 1; return fibonacci(n-1) + fibonacci(n-2); } |
Now if you enter 15, the program will display the following output:
1 2 3 4 5 | --- Fibonacci series program --- Enter a number:15 Fibonacci series: 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 |
C Program for Fibonacci series using iteration
The Fibonacci series program using recursion technique is less efficient if you want to display a long series because the number of function calls increase and the chance of a stack overflow error may occur.
The following is the program that displays the Fibonacci series using iteration technique:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | #include <stdio.h> typedef unsigned long long F; F fibonacci(F n); int main() { int n, i, j; printf("--- Fibonacci series program ---\n"); printf("Enter a number:"); scanf("%d",&n); printf("\nFibonacci series:\n"); j = 0; for ( i = 1 ; i <= n ; i++ ) { printf("%d ", fibonacci(j)); j++; } } F fibonacci(F n) { int i; F f1 = 0; F f2 = 1; F fi; if(n == 0) return 0; if(n == 1) return 1; for(i = 2 ; i <= n ; i++ ) { fi = f1 + f2; f1 = f2; f2 = fi; } return fi; } |
In this tutorial, you have learned how to develop a C program for Fibonacci series using recursion and iteration techniques.