这个函数是递归的，即使它不调用自己？

Question

from pythonds.basic.stack import Stack

rStack = Stack()

def toStr(n,base):
    convertString = "0123456789ABCDEF"
    while n > 0:
        if n < base:
            rStack.push(convertString[n])
        else:
            rStack.push(convertString[n % base])
        n = n // base
    res = ""
    while not rStack.isEmpty():
        res = res + str(rStack.pop())
    return res

print(toStr(1345,2))

我指的是本教程，并粘贴了上面的代码。教程说这个函数是递归的，但是我在任何地方都没有看到递归调用，只是一个while循环。我遗漏了什么？

Answer 1

根据定义，是一种方法，其中问题的解决取决于同一问题的较小实例的解决方案。是一种递归算法。

在这里，问题是如何用给定的符号将数字转换为字符串。

函数对数据的“存储”实际上如下所示：

push(d1)
push(d2)
...
push(dn-1)
push(dn)

res+=pop(dn)
res+=pop(dn-1)
...
res+=pop(d2)
res+=pop(d1)

这实际上是：

def pushpop():
    push(dx)
    pushpop(dx+1...dn)
    res+=pop(dx)

例如，处理特定数据块的步骤包含处理数据其余部分的所有步骤(每个块以相同的方式处理)。

如果函数是递归的(因为它们倾向于将该术语应用于狭义的子例程)，这是可以争论的，但是它实现的算法肯定是。

为了让您更好地感受到不同之处，下面是相同问题的迭代解决方案：

def toStr(n,base):
    charmap = "0123456789ABCDEF"
    res=''
    while n > 0:
        res = charmap[n % base] + res
        n = n // base
    return res

如您所见，该方法不存储任务，因此内存占用要低得多。这就是不同之处:迭代算法使用相同的状态实例执行每个步骤，方法是对其进行变异，而递归算法则为每个步骤创建一个新实例，如果仍然需要旧实例，则必须将它们存储起来。

Answer 2

因为你用的是堆栈结构。

如果考虑函数调用是如何实现的，递归本质上是一种让编译器为您管理调用堆栈的简单方法。

这个函数手动处理所有的堆栈，但在概念上仍然是一个递归函数，只是一个手动执行堆栈管理的函数，而不是让编译器执行它。