修复关于递归的知识差距：基本条件和状态

Question

我对递归的知识有差距。我知道基本情况应该终止递归，但我很难选择正确的。

此外，我在理解如何在不更新方法签名的情况下管理状态时遇到问题。

以largest adjacent element products的问题为例。我对分而治之的理解是：

1) divide the problem into smaller problems:
    1.1) create a left array of the first two elements
    1.2) create a right array by removing the first element
2) conquer by recursion:
    2.1) repeat the function on the right array
    2.2) choose a good base case to terminate
3) combine the solution
    3.1) this is where things get tricky!? 
    3.2) for the task of multiplication, how do I persist the result
    after each recursion when each new call will re-instantiate the
    result list

这个知识差距的一个具体例子如下：我选择的base case是当列表的元素少于两个时，然后是return0。当两个元素的乘积为 less than 0.

时，当然可以 except

为基本情况返回None是状态有问题，因为在python3中None和int比较会抛出错误。

TypeError: '>=' not supported between instances of 'int' and 'NoneType'

完整代码如下

def multiply(inputArray):
    m = inputArray[0] * inputArray[1]
    return m

def adjacentElementsProduct(inputArray):
    # [3, 6, -2, -5, 7, 3]
    if len(inputArray) <= 1:
        # return 0
        return None

    left = inputArray[:2]
    right = inputArray[1:]
    result = []

    result.append(adjacentElementsProduct(right))
    m = multiply(left)

    print(result, left, m)

    if len(result) == 0:
        result.append(m)
    else:
        if m >= result[0]:
            result.insert(0, m)

    return result[0]

Answer 1

看来您的主要问题是如何组合解决方案。在每次迭代中，您需要组合的是左数组和右数组的结果。

how do I persist the result?

只是 return 左结果和右结果的最大值。

def adjacentElementsProduct(inputArray):
    # [3, 6, -2, -5, 7, 3]
    if len(inputArray) <= 1:
        return None

    left = inputArray[:2]
    right = inputArray[1:]

    m = multiply(left)

    result = adjacentElementsProduct(right)

    # combine solutions
    if result is None:
        return m
    else:
        return max(m, result)

测试用例：

print(adjacentElementsProduct([3]))
None
print(adjacentElementsProduct([3,6]))
18
print(adjacentElementsProduct([3, 6, -2, -5, 7, 3]))
21

修复关于递归的知识差距：基本条件和状态

Fixing Gap in Knowledge about recursion: base conditions and state

recursion

divide-and-conquer

python-3.x