Pythonの再帰と変数のスコープ

Question

私はこのLeetCodeの問題Palindrome Partitioningの解決方法を見つけようとしています。これは私が現在持っているものです。

def partition(s): 
    out = [] 
    def isPalindrome(word): 
     return word == word[::-1] 

    def addPalindrome(word, start, partition): 
     if start == len(word): 
      out.append(partition) #where I append to 'out' 
      print out, partition # where I print the finished partition 
      return 
     for i in range(start+1, len(word)+1): 
      sub = word[start:i] 
      if isPalindrome(sub): 
       partition.append(sub) 
       addPalindrome(word, i, partition) 
       partition.pop() 

    if not s: 
     return [] 
    addPalindrome(s, 0, []) 
    return out 

print partition('aaa') 

入力「AAA」への正しい解決策が[['a', 'a', 'a'], ['a', 'aa'], ['aa', 'a'], ['aaa']]です。ベースケースにpartitionを印刷すると、正しいと思われます。私はそれらを再帰の範囲外にして正しく返すべき変数outに追加しています。

ただし、これは該当しません。このことになる基本ケースでoutを印刷する理由を私は理解していない：outを返すとき

[['a', 'a', 'a']] 
[['a', 'aa'], ['a', 'aa']] 
[['aa', 'a'], ['aa', 'a'], ['aa', 'a']] 
[['aaa'], ['aaa'], ['aaa'], ['aaa']] 

は最後に、空の配列を返すようです。何が起きてる？

再帰後の出力outは[[], [], [], []]です。

この

はPython2.7

Answer 1

私はある見る問題である1）成長の結果を保存するにコピーする（コメントで言及されたように）と2）グローバルの使用を節約するために覚えるのではなくハンドリングそれは再帰の中で起こる。コードを単純化してみましょうとの両方の問題を修正：再帰内ではなく、グローバルとして結果を渡すとき

def isPalindrome(word): 
    return word == word[::-1] 

def addPalindrome(word, start, partitions): 
    result = [] 

    if start == len(word): 
     result.append(list(partitions)) # where I append to 'out' 
    else: 
     for i in range(start+1, len(word)+1): 
      sub = word[start:i] 

      if isPalindrome(sub): 
       partitions.append(sub) 
       result.extend(addPalindrome(word, i, partitions)) 
       partitions.pop() 
    return result 

def partition(s): 
    out = [] 

    if s: 
     out = addPalindrome(s, 0, []) 

    return out 

print partition('aaa') 

、キーは*.append()にするとき知っていると時に成長している結果を*.extend()します。