面试题：C++递归函数实现斐波那契数列

Question

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

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$，除了$n = 0$和$n = 1$的情况，函数都会调用自身两次，形成一个深度为$n$的递归树，树的节点数随着$n$指数增长。

空间复杂度分析

空间复杂度为$O(n)$。因为递归调用栈的深度最大为$n$，每次递归调用会占用一定的栈空间，所以空间复杂度取决于递归调用栈的深度。