两种方法求斐波拉切数列的第N个数c语言代码

在C语言中，可以使用递归和动态规划两种方法来求斐波那契数列的第N个数。

**1. 递归法（递归函数实现）：**

#include <stdio.h>

// 递归计算斐波那契数
int fibonacci_recursive(int n) {
    if (n <= 0)
        return 0;
    else if (n == 1 || n == 2)
        return 1;
    else
        return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);
}

int main() {
    int N, i;
    printf("Enter the position of the Fibonacci number: ");
    scanf("%d", &N);
    
    // 输出结果
    if (N >= 0) {
        printf("The %dth Fibonacci number is: %d\n", N, fibonacci_recursive(N));
    } else {
        printf("Invalid input. Please enter a non-negative number.\n");
    }

    return 0;
}

**2. 动态规划法（循环数组实现）：**

#include <stdio.h>
#define MAX 100

// 使用动态规划计算斐波那契数
int fibonacci_dp(int n) {
    int fib[MAX];
    fib[0] = 0;
    fib[1] = 1;

    for (int i = 2; i <= n; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
    
    return fib[n];
}

int main() {
    int N;
    printf("Enter the position of the Fibonacci number: ");
    scanf("%d", &N);

    // 输出结果
    if (N >= 0 && N < MAX) {
        printf("The %dth Fibonacci number is: %d\n", N, fibonacci_dp(N));
    } else {
        printf("Invalid input. Please enter a number less than %d.\n", MAX);
    }

    return 0;
}

这两种方法各有优缺点。递归简单易懂，但效率较低，因为存在大量重复计算；而动态规划则避免了重复，时间复杂度更低，但对于较大的`N`可能会导致栈溢出。