python - 是否可以从此函数中删除递归？

Question

我已经玩了一段时间了，就是看不到明显的解决方案。我想从 XinY_Go 函数中删除递归。

def XinY_Go(x,y,index,slots):
   if (y - index) == 1:
      slots[index] = x
      print slots
      slots[index] = 0
      return
   for i in range(x+1):
      slots[index] = x-i
      XinY_Go(x-(x-i), y, index + 1, slots)

def XinY(x,y):
   return XinY_Go(x,y,0,[0] * y)

该函数正在计算将 X 弹珠放入 Y 槽的方法数。这是一些示例输出:

 >>> xy.XinY(1,2)
 [1, 0]
 [0, 1]
 >>> xy.XinY(2,3)
 [2, 0, 0]
 [1, 1, 0]
 [1, 0, 1]
 [0, 2, 0]
 [0, 1, 1]
 [0, 0, 2]

Answer 1

我们认为递归的一切也可以被认为是基于堆栈的问题，其中递归函数只使用程序的调用堆栈，而不是创建一个单独的堆栈。这意味着任何递归函数都可以使用堆栈来重写。

我对 python 的了解还不够深，无法为您提供实现，但这应该能为您指明正确的方向。但简而言之，将函数的初始参数压入堆栈并添加一个只要堆栈大小大于零就运行的循环。每次循环迭代弹出一次，每次函数当前调用自身时推送。