递归求正方形的面积

Question

我有一个大正方形，它是由固定大小的小square-tiles组成的。

这些小square-tiles的面积是已知的。

其中一个图块显示在左上角。

现在，

每个方格可以分解成4个子方格。每个方块都有一个标识方块的键。

big-square 中可能有很多空方块。在这些情况下，密钥不存在，该区域被视为零。

最小的图块的密钥长度为 3。

我想递归地找到给定一个键的任何正方形的面积。

这就是我正在尝试的。但它没有给我正确的解决方案。

findAreaRecursive(self, key, maxDepth=3):
    if len(Key) == maxDepth:
        if self.keyExists(key):
           return self.getAreaValue(key)
        else:
           return 0

    else:


        keyChild0 = key + '0'
        keyChild1 = key + '1'
        keyChild2 = key + '2'
        keyChild3 = key + '3'

        if self.keyExists(keyChild0): 
            areaChild0 = self.findAreaRecursive(keyChild0, maxDepth)
        else:
            areaChild0 = 0

        if self.keyExists(keyChild1): 
            areaChild1 = self.findAreaRecursive(keyChild1, maxDepth)
        else:
            areaChild1 = 0

        if self.keyExists(keyChild2): 
            areaChild2 = self.findAreaRecursive(keyChild2, maxDepth)
        else:
            areaChild2 = 0

        if self.keyExists(keyChild3): 
            areaChild3 = self.findAreaRecursive(keyChild3, maxDepth)
        else:
            areaChild3 = 0

        return areaChild0 + areaChild1 + areaChild2 + areaChild3

我做错了什么。我是递归的新手。欢迎任何帮助。

Answer 1

在我看来，您的递归查找器有点过于复杂。你有点像在函数中展开递归。下面是一个可能 'purely' 递归的例子。如果我假设 keyExists() 通过在键有区域值时返回 true 来工作，它就会工作。

def findAreaRecursive(self, key, maxDepth=3):
    totArea = 0
    if len(key) == maxDepth:
        if self.keyExists(key):
           totArea += self.getAreaValue(key)
    else:
        for i in range(4):
            newKey = key + str(i)
            totArea += findAreaRecursive(self, newKey, maxDepth)

    return totArea

然而……

递归可能很难理解。如果您想继续采用您的方法，可以通过

帮助澄清您的问题

放入整个代码 - 包括 getAreaValue() 和 keyExists() 函数，我们可以查看它以找出执行路径和失败的地方。例如，您我们看不到您的 keyExists() 函数的逻辑，也许这有时会给出错误的值，导致您的代码的一个分支在您不期望的时候返回零。
在递归中放入一些打印语句（好的，因为在您的情况下递归不是太深）。你会看到发生了什么。我将从打印语句开始作为函数中的第一个语句
```
print "Called with key",key
```
这将允许您跟踪正在调用哪些键，并且您可以检查它是否按照您期望的顺序发生。

编辑：

另请参阅 this answer 一个类似的问题，该问题首先很好地总结了一种思考递归的方法，因为您说您是递归的新手。

递归求正方形的面积

find area of a square recursively

python

recursion

quadtree