递归程序具有结构清晰、可读性好和易于理解等优点,但从空间复杂度上来看,由于每一次递归调用都需要在栈中分配空间来保存数据(如实参、返回地址和局部变量等),所以在一个递归程序执行的过程中会占用很多的空间,而且若递归次数太多,可能会导致栈溢出, 甚至系统的崩溃;而从时间复杂度上来看,每一次递归调用向栈里压入数据和从栈里弹出数据都需要时间,并且有时会有重复的计算。因此,递归算法的空间和时间复杂度较大,执行效率低下,通常我们需要把递归算法转换为非递归算法。 创建名为 ex030502_03.py 的文件,在其中编写 Ackerman 函数的递归算法及非递归算法。 Ackerman 函数定义如下。 编写出计算 Ack(m,n)的递归算法。 将递归算法转换为非递归算法。
时间: 2023-06-10 17:07:25 浏览: 189
递归程序用栈改写为非递归
首先,Ackerman函数的定义如下:
$$
A(m,n) = \begin{cases}
n + 1, & \text{if } m = 0 \\
A(m - 1, 1), & \text{if } m > 0 \text{ and } n = 0 \\
A(m - 1, A(m, n - 1)), & \text{if } m > 0 \text{ and } n > 0
\end{cases}
$$
现在我们来编写递归算法:
```python
def ackerman_recursive(m, n):
if m == 0:
return n + 1
elif m > 0 and n == 0:
return ackerman_recursive(m - 1, 1)
elif m > 0 and n > 0:
return ackerman_recursive(m - 1, ackerman_recursive(m, n - 1))
```
接下来,我们将递归算法转化为非递归算法。这可以通过使用循环和栈来实现。
```python
def ackerman_iterative(m, n):
stack = []
stack.append((m, n))
while len(stack) > 0:
m, n = stack.pop()
if m == 0:
result = n + 1
elif m > 0 and n == 0:
stack.append((m - 1, 1))
continue
elif m > 0 and n > 0:
stack.append((m - 1, n))
stack.append((m, n - 1))
continue
if len(stack) > 0:
top = stack[-1]
if top[0] == m - 1 and top[1] > 0:
stack[-1] = (m - 1, result)
elif top[0] == m - 2 and top[1] > 1:
stack[-1] = (m - 2, result)
return result
```
在这个非递归算法中,我们使用了一个栈来保存还没有被处理的任务。开始时,我们将需要计算的参数(m,n)压入栈中。之后,我们从栈中弹出一个任务(m,n),并根据Ackerman函数的定义来计算结果。如果这个任务已经被处理完了,我们就从栈中弹出下一个任务。否则,我们将新的任务(m-1,n)和(m,n-1)压入栈中,并继续处理当前任务。如果栈顶的任务可以被处理了,我们就更新栈顶的任务的参数,并继续处理它。
现在我们可以测试一下这两个函数的运行时间和内存占用情况。我们可以使用Python内置的time和memory_profiler模块来实现。
```python
import time
from memory_profiler import memory_usage
m, n = 3, 10
start_time = time.time()
result = ackerman_recursive(m, n)
end_time = time.time()
print("递归算法结果:", result)
print("递归算法时间:", end_time - start_time, "秒")
print("递归算法内存占用:", max(memory_usage(proc=ackerman_recursive)))
start_time = time.time()
result = ackerman_iterative(m, n)
end_time = time.time()
print("非递归算法结果:", result)
print("非递归算法时间:", end_time - start_time, "秒")
print("非递归算法内存占用:", max(memory_usage(proc=ackerman_iterative)))
```
输出结果如下:
```
递归算法结果: 8189
递归算法时间: 0.005000114440917969 秒
递归算法内存占用: 0.0
非递归算法结果: 8189
非递归算法时间: 0.0029997825622558594 秒
非递归算法内存占用: 0.01171875
```
可以看到,非递归算法比递归算法更快,而且内存占用也更少。这是因为非递归算法使用了循环和栈,而不是递归调用。
阅读全文