递归栈空间（Recursion Stack Space）是在计算机程序中用于存储和跟踪递归调用的内存空间。递归是一种在函数或方法中调用自身的技术，通常用于解决需要重复执行相同或类似操作的问题。递归栈空间用于存储递归调用的信息，包括函数的参数、局部变量和返回地址等。
使用递归栈空间的一般步骤如下：
- 当一个函数被递归调用时，将其相关信息（如参数、局部变量和返回地址）存储在递归栈空间中。
- 函数执行完毕后，从递归栈空间中移除相关信息。
- 如果递归调用仍在进行中，程序将继续在递归栈空间中存储和检索相关信息。
以下是一个简单的递归示例，演示了如何在 Python 中使用递归栈空间：
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)
result = factorial(5)
print("Factorial of 5 is:", result)
CopyCopy
在这个示例中，我们定义了一个名为 factorial 的递归函数，用于计算给定整数 n 的阶乘。当我们调用 factorial(5) 时，程序将执行以下操作：
- 将参数 n（值为 5）和局部变量 result 存储在递归栈空间中。
- 调用 factorial(5-1)，将新的参数 n-1（值为 4）存储在递归栈空间中。
- 在 factorial(4) 函数内部，计算 4 * factorial(3)。由于 factorial(3) 仍在递归调用中，因此程序将在递归栈空间中查找 factorial(3) 的相关信息。
- 递归调用继续进行，直到 factorial(0) 被调用。此时，递归栈空间中的信息为 factorial(0) 的相关信息。
- factorial(0) 返回 1，将其存储在局部变量 result 中。
- 递归调用结束，程序从递归栈空间中移除所有相关信息。
- 最后，打印计算出的 result 值，即 5 的阶乘。
场景案例:
计算阶乘
递归实现:
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)
CopyCopy
循环实现:
def factorial(n):
result = 1
for i in range(1, n+1):
result *= i
return result
CopyCopy
在计算阶乘这个场景中，递归实现更加简洁易懂，而循环实现则更加高效，因为递归调用需要维护函数调用栈，而循环实现则不需要。
Demo:
下面是一个使用递归栈空间的 Demo 程序，用于计算斐波那契数列的第 n 项:
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
n = 10
print("斐波那契数列的第 {} 项为:{}".format(n, fibonacci(n)))
CopyCopy
在这个程序中，我们使用递归实现了斐波那契数列的计算，当计算第 10 项时，程序会调用自身 9 次，每次调用都会在栈中添加一层新的栈帧，用于存储函数的局部变量、参数和返回地址等信息。当计算结束时，栈帧会从栈中弹出，释放所占用的内存空间。
