再帰に関する知識のギャップを修正する：基本条件と状態

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リストよりも少ない2つの要素を有する場合、次いで0を返すあります。もちろん、2つの要素の積がless than 0の場合はexceptとなります。

には、intの比較でエラーが発生するため、Noneをベースケースに戻すと状態に問題があります。

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

はあなたのように見えるの下に主な問題は、解決策をどのように組み合わせるかです。すべての単一反復で、結合する必要があるのは左配列と右配列の結果です。

どのように結果を保持しますか？

左の結果と正しい結果の最大値を返します。

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