fibonacci数列第n项递归算法

Fibonacci数列是指：1、1、2、3、5、8、13、21、34、55、89、144……，其中每一项都是前两项的和。递归算法实现如下：

int fibonacci(int n) {
    if (n <= 2) {
        return 1;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

该递归算法的时间复杂度为 O(2^n)，因为每次都会调用两次自身。对于较大的 n，递归算法会非常耗时，因此更好的实现方式是使用迭代算法或者记忆化搜索。