递归求正方形的面积

find area of a square recursively

我有一个大正方形,它是由固定大小的小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

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

在我看来,您的递归查找器有点过于复杂。你有点像在函数中展开递归。下面是一个可能 '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

然而……

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

帮助澄清您的问题
  1. 放入整个代码 - 包括 getAreaValue() 和 keyExists() 函数,我们可以查看它以找出执行路径和失败的地方。例如,您我们看不到您的 keyExists() 函数的逻辑,也许这有时会给出错误的值,导致您的代码的一个分支在您不期望的时候返回零。

  2. 在递归中放入一些打印语句(好的,因为在您的情况下递归不是太深)。你会看到发生了什么。我将从打印语句开始作为函数中的第一个语句

    print "Called with key",key
    

    这将允许您跟踪正在调用哪些键,并且您可以检查它是否按照您期望的顺序发生。

编辑:

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