價值在帕斯卡三角的每一行 - 遞歸

Question

在下面的代碼：

def pascal_row(row): 
    if row == 0: 
     return [1] 
    previous_row = pascal_row(row - 1) 
    pairs = zip(previous_row[:-1], previous_row[1:]) 
    return [1] + map(sum, pairs) + [1] 

如果我print (pascal_row(5))，它返回[1, 5, 10, 10, 5, 1]這是正確的解決方案。

這是一項家庭作業，我們需要使用遞歸，並且不能使用任何循環或zip。

有人可以幫我轉換它嗎？謝謝！

Answer 1

您可以使用不同的遞歸函數sliding_sum來計算前一行的成對和。然後，在任一端添加[1]。

def sliding_sum(someList): 
    if len(someList) == 1: 
     return [] 
    return [someList[0] + someList[1]] + sliding_sum(someList[1:]) 

def pascal_row(row): 
    if row == 0: 
     return [1] 
    previous_row = pascal_row(row-1) 
    new_row = [1] + sliding_sum(previous_row) + [1] 
    return new_row 

for i in range(6): 
    print pascal_row(i) 

輸出

[1] 
[1, 1] 
[1, 2, 1] 
[1, 3, 3, 1] 
[1, 4, 6, 4, 1] 
[1, 5, 10, 10, 5, 1] 

Answer 2

這裏的涉及一個輔助函數另一種解決方案：

def pascal_row(row): 
    if row == 0: 
     return [1] 
    return _pascal_row(row, 0, [1]) 

def _pascal_row(target_row, current_row, res): 
    if target_row == current_row: 
     return res 
    else: 
     res = [1] + [res[i] + res[i+1] for i in xrange(len(res) - 1)] + [1] 
     return _pascal_row(target_row, current_row + 1, res) 

print pascal_row(5) # [1, 5, 10, 10, 5, 1]