Value for each row in Pascal Triangle - Recursion

Question

In the following code:

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]

if I print (pascal_row(5)), it returns [1, 5, 10, 10, 5, 1] which is the correct solution.

This is a homework assignment where we need to use recursion, and cannot use any loops or zip.

Could someone please help me convert it accordingly? Thank you!

Answer 1

You can use a different recursive function sliding_sum in order to calculate the pairwise sum for the previous row. Then, just append [1] on either end.

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)

Output

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