面试题：C++递归函数复杂度分析之斐波那契数列

Question

请写出计算斐波那契数列第n项的C++递归函数，并分析该递归函数的时间复杂度和空间复杂度。斐波那契数列的定义为：F(0)=0，F(1)=1，F(n)=F(n - 1)+F(n - 2)（n>=2）。

Answer 1

#include <iostream>

// 计算斐波那契数列第n项的递归函数
int fibonacci(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

时间复杂度分析

该递归函数的时间复杂度为$O(2^n)$。因为在递归调用中，每次调用都会产生两个新的递归调用，形成一个高度为n的递归树，节点数近似为$2^n$。

空间复杂度分析

空间复杂度为$O(n)$。由于递归调用需要占用栈空间，在最坏情况下，递归深度为n，所以空间复杂度取决于递归调用的深度。