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

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))

我指的是this tutorial，还粘贴了上面的代码。教程说这个函数是递归的，但是我没有看到递归调用，只有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)

有效地：

^{pr2}$

即，处理特定数据块的步骤包含处理其余数据的所有步骤（每个数据块的处理方式相同）。在

如果函数是递归的（因为它们倾向于在狭义上将该术语应用于子例程），但它实现的算法肯定是递归的。在

---

为了让您更好地感受到差异，下面是一个针对同一问题的迭代解决方案：

^{3}$

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

Answer 2

你是对的，这个特殊的函数不是递归的。然而，上下文是，在上一张幻灯片上有一个递归函数，在这张幻灯片中，他们想展示一下它的内部行为。他们后来说：

The previous example ^{[i.e. the one in question - B.]} gives us some insight into how Python implements a recursive function call.

所以，是的，标题有误导性，它应该是扩展递归函数或用堆栈模仿递归函数行为，或者类似这样的东西。在

可以说，这个函数在某种意义上使用了递归方法/策略来解决所要解决的问题，但它本身并不是递归的。在

Answer 3

因为你使用的是堆栈结构。在

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

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