写出斐波那契数列的非递归算法

斐波那契数列是一个数列，其中每个数字都是前两个数字之和，通常从0和1开始。非递归算法是通过循环而不是函数的嵌套调用来计算这个序列，这样可以避免函数调用带来的性能开销。以下是使用迭代方法（也称为循环）来计算斐波那契数列的一个例子：

def fibonacci_non_recursive(n):
    if n <= 0:
        return "输入的数值必须大于0"
    elif n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        a, b = 0, 1
        for _ in range(2, n+1):
            a, b = b, a + b
        return b

# 示例
print(fibonacci_non_recursive(10))  # 输出：55

在这个算法中，我们首先检查基本情况，然后初始化变量a和b作为斐波那契序列的前两个元素。接着，我们在循环中逐步更新这两个值，直到达到目标位置n。

相关问题

写出求斐波那契数列的递归算法。

斐波那契数列是一种经典的递归序列，其中每个数都是前两个数之和。在Java中，我们可以这样定义一个递归函数来计算第n个斐波那契数：

public class Fibonacci {
    public static void main(String[] args) {
        int n = 6; // 要求的第n个斐波那契数，可以更改这个值
        long fib = fibonacci(n);
        System.out.println("The " + n + "th Fibonacci number is: " + fib);
    }

    // 递归函数计算斐波那契数
    public static long fibonacci(int n) {
        if (n <= 1) {
            return n; // 基本情况，第一个和第二个斐波那契数分别为0和1
        } else {
            return fibonacci(n - 1) + fibonacci(n - 2); // 递归调用，当前数是前两个数的和
        }
    }
}

注意：由于递归涉及大量的重复计算，对于大的n值，这种方法效率较低。实际应用中，通常会使用动态规划等非递归方法来提高效率。

3.斐波那契(Fibonacci)数列的定义为:它的第 1项和第 2项分别为0和1,以后各项为其前两项之和。若斐波那契数列中的第 n 项用 Fb(n)表示，试编写出计算 Fib(n)的递归算法和非递归算法,以及求出各自的时间和空间复杂度 long Fib(int n);//求斐波那契数列中第 n项的递归算法 long FibN(int n); //求斐波那契数列中第 n项的非递归算法

递归算法：

long Fib(int n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    return Fib(n - 1) + Fib(n - 2);
}

递归算法的时间复杂度为 O(2^n)，空间复杂度为 O(n)。

非递归算法：

long FibN(int n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    long f1 = 1, f2 = 1, f3 = 0;
    for (int i = 3; i <= n; i++) {
        f3 = f1 + f2;
        f1 = f2;
        f2 = f3;
    }
    return f3;
}

非递归算法的时间复杂度为 O(n)，空间复杂度为 O(1)。