python如何实现递归转非递归

当一个算法或者函数使用递归时，它会在内存中伸展出一条递归链，最后达到解决问题的结束点，这条链往往是以下几个步骤的简单重复：

1. 检查基本条件。
2. 执行一些操作或者递归。 3. 更改输入参数。

递归可以使代码更加简洁和容易理解，但是递归链太长时，会消耗大量的内存资源，并且很难理清楚所有的递归过程，所以我们有必要将递归函数转换成非递归函数。

下面介绍两种将递归函数转化为非递归函数的方法：

方法一：使用栈

我们可以手动使用栈来模拟递归过程，通过压栈和出栈的方式代替递归。我们定义一个Stack类，并实现push()，pop()，isEmpty()方法，然后把每次递归中要处理的参数都压入栈中，而每一层处理完之后从栈里面取出值。这种方法虽然比较直接，但是对于复杂的函数，还是不够灵活。

比如这是一个递归实现斐波那契数列的函数：

def fib(n):
    if n == 0 or n == 1:
        return n
    return fib(n-1) + fib(n-2)

现在我们来用栈来实现：

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def isEmpty(self):
        return len(self.items) == 0

def fib(n):
    s = Stack()
    s.push(n)
    sum = 0
    while s.isEmpty() == False:
        num = s.pop()
        if num == 0 or num == 1:
            sum += num
        elif num > 1:
            s.push(num - 1)
            s.push(num - 2)

    return sum

方法二：使用尾递归

尾递归是一种特殊形式的递归，它的最后一个操作是一个递归调用。如果函数返回递归调用的结果，并且任何其他操作都没有处理递归调用的结果，那么我们称它为尾递归。尾递归可以转换为迭代，因为它们不需要在函数调用之间保留任何状态。

以下是一个递归实现阶乘的函数：

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n-1)

现在我们要将其转化为尾递归形式。我们可以使用两个参数：一个跟踪我们乘到哪个数字了，另一个跟踪我们已经计算了多少。这里的尾递归就是将积作为一个参数传递，递归的乘法操作会依此更新积的值。这样，递归链就被消除了。

def factorial(n,acc=1):
    if n == 0:
        return acc
    return factorial(n-1,acc*n)

总之，我们可以将尾递归形式转换成迭代形式，转换过程中需要注意的是： 1. 参数维护。将每个函数调用之前的状态都保存到参数中。 2. 操作维护。非递归实现需要迭代执行所有操作。