Calculating Fibonacci Sequence in C Language

The Fibonacci sequence is a classic mathematical sequence characterized by the fact that the first two numbers are 1 and 1, and from the third number onward, each number is the sum of the two preceding ones. The sequence is as follows: 1, 1, 2, 3, 5, 8, 13, 21, …

Method 1: Using Loops (Iterative Method)

This is the most efficient method, with a time complexity of O(n) and a space complexity of O(1).

#include <stdio.h>
// Output the first n terms of the Fibonacci sequence
void fibonacci(int n) {
    int first = 1, second = 1;
    int next;
    // Handle special cases
    if (n <= 0) {
        printf("Please enter a positive integer\n");
        return;
    } else if (n == 1) {
        printf("The first term of the Fibonacci sequence: %d\n", first);
        return;
    }
    // Output the first two terms
    printf("The first %d terms of the Fibonacci sequence: %d, %d", n, first, second);
    // Loop to calculate and output subsequent terms
    for (int i = 3; i <= n; i++) {
        // The next term is the sum of the previous two terms
        next = first + second;
        printf(", %d", next);
        // Update the values of the previous two terms
        first = second;
        second = next;
    }
    printf("\n");
}
int main() {
    int num;
    printf("Please enter the number of Fibonacci sequence terms to output: ");
    scanf_s("%d", &num);
    fibonacci(num);
    return 0;
}

Code Analysis:

Define first and second to represent the first two terms of the sequence (initial values are both 1)
Handle special cases: when n=1, only output the first term
Loop to calculate each term starting from the 3rd term:

The next term next = the sum of the previous two terms (first + second)
Update the values of first and second for the next calculation

Output the calculated results sequentially

Method 2: Using Recursion

The recursive method has concise code but lower efficiency, with a time complexity of O(2^n), making it unsuitable for calculating larger n values.Disadvantage: There is a lot of repeated calculations (for example, calculating fib(5) requires calculating fib(4) and fib(3), and calculating fib(4) again requires calculating fib(3))

Method 3: Using Arrays for Storage (Memoization)

#include <stdlib.h>
#include <stdio.h>
// Use an array to calculate and output the first n terms of the Fibonacci sequence
void fibonacci(int n) {
    int* fib = (int*)malloc(n * sizeof(int));
    if (fib == NULL) {
        printf("Memory allocation failed\n");
        return;
    }
    // Initialize the first two terms
    if (n >= 1) fib[0] = 1;
    if (n >= 2) fib[1] = 1;
    // Calculate subsequent terms
    for (int i = 2; i < n; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
    // Output results
    printf("The first %d terms of the Fibonacci sequence: ", n);
    for (int i = 0; i < n; i++) {
        printf("%d", fib[i]);
        if (i < n - 1) {
            printf(", ");
        }
    }
    printf("\n");
    // Free memory
    free(fib);
}

Comparison of the Three Methods

Method	Time Complexity	Space Complexity	Advantages	Disadvantages
Iterative Loop	O(n)	O(1)	Highest efficiency, low memory usage	Cannot directly access any term
Recursion	O(2^n)	O(n)	Concise code, aligns with mathematical definition	Low efficiency, unsuitable for large n
Array Storage	O(n)	O(n)	Can directly access any term	Uses additional memory

Conclusion

For general applications, it is recommended to use the iterative method, which combines efficiency and low memory usage
The recursive method is mainly used to understand the concept of recursion and is rarely used in practical applications
The array storage method is suitable for scenarios where multiple different terms in the sequence need to be accessed