递归函数的时间复杂度怎么算

递归函数的时间复杂度可以通过递推式来求解。我们可以先分析递归函数的每一层时间复杂度，然后根据递归深度得出总的时间复杂度。

具体来说，我们可以先写出递推式，然后使用数学归纳法证明递推式的正确性。最后，我们可以根据递推式来分析时间复杂度。

以斐波那契数列为例，递推式为：F(n) = F(n-1) + F(n-2)，其中 F(0) = 0，F(1) = 1。

我们可以使用递归函数来求解斐波那契数列：

int fib(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    return fib(n-1) + fib(n-2);
}

假设递归深度为 d，每层的时间复杂度为 T，则总的时间复杂度为 O(T*d)。

对于斐波那契数列的递归函数，每次递归都会调用两次自身，因此有 T(n) = T(n-1) + T(n-2) + O(1)。根据递推式，我们可以得到 T(n) = O(2^n)。

因此，递归函数 fib 的时间复杂度为 O(2^n * d)。