0

我正在尝试自学python，并且在递归时遇到了困难。我已经完成了经典的递归函数（阶乘、斐波那契数......），但我将回顾旧代码并尝试将我的大部分迭代函数转换为递归函数以进行练习。

这是我撞到的墙：

不久前我做了一个地牢爬行者，我正在尝试替换一个用于显示精灵附近方块的 for 循环。因此，当放置精灵时，他/她会看到他/她所在的瓷砖以及相邻和对角线方块（总共 9 个，包括头像所在的那个）。构成房间的其他瓷砖被隐藏了。这我认为是视野半径 1。对于视野半径 2，我希望 char 看到半径为 1 的正方形以及与这些瓷砖相邻的所有瓷砖。当时我不知道如何使用 for 循环来做到这一点，所以我只实现了一个更简单的方案。

我觉得这个可见性函数可以递归编写，但我很难想出一个基本案例以及我的递归步骤是什么。我的 for 循环只是取了化身 pos 并在一个范围内迭代到化身 pos + 半径，我为 x,y 坐标做了这个。

至于将其转换为递归函数，我真的很困惑。我进行了许多搜索，试图获得领先，但只提出了复杂的主题，例如：使用递归阴影投射的 FOV，这远远超出了我的范围。

任何帮助将不胜感激。

4

2 回答 2

1

我发现用文字表达递归很有帮助。该算法所说的基本上是“在半径 N 处可见的是从半径 N-1 处可见的”。就像，呃，边缘变大了。

于 2012-10-13T03:02:41.497 回答
0

像这样的东西怎么样：

def visible(pos, radius, seen):
    if radius == 1:
        # base case
        seen.add(...)
        yield ...
    else:
        for center in visible(pos, radius-1, seen):
            for x in visible(center, 1, seen):
                if x not in seen:
                    seen.add(x)
                    yield x

seen将是一个set. 每次您visible“从外部”调用时，您都会提供一个空集：

visible(pos, radius, set())

该seen集合也可以被初始化以实现战争迷雾（或至少奇怪的看不见的方块；））......

于 2012-10-12T21:54:34.213 回答