递归的空间复杂度和时间复杂度

递归的空间复杂度和时间复杂度取决于递归的深度和每次递归所需的空间。假设每次递归所需的空间为常量，那么递归的空间复杂度将与递归的深度成正比。而递归的时间复杂度则与递归的深度和每次递归所需的时间成正比。

例如，考虑一个简单的递归函数，计算斐波那契数列的第n个数：

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

每次递归需要常量空间，递归的深度为n。因此，递归的空间复杂度为O(n)，时间复杂度也为O(2^n)。

需要注意的是，有些递归算法可能会重复计算相同的值，这种情况下可以使用记忆化搜索来优化递归算法的时间复杂度。