递归函数空间复杂度分析：int fun(int n) 示例

本文将分析以下递归函数的空间复杂度：

int fun(int n) {
int x = 100;
if (n == x)
return n;
else
return fun(++n);
}

该函数的逻辑是，当 n 等于 100 时返回 n，否则递归调用自身，并将 n 加 1。

空间复杂度分析：

由于该函数是递归的，每次调用自身都会在堆栈中创建一个新的栈帧。当 n 不等于 100 时，函数会不断递归调用自身，直到 n 等于 100。这意味着函数调用次数与 n 的大小成正比。因此，该函数的空间复杂度为 O(n)。

总结：

递归函数 int fun(int n) 的空间复杂度为 O(n)，因为每次递归调用都会在堆栈中创建一个新的栈帧，而调用次数与 n 的大小成正比。