Write hosoya's triangle in Python

See more:

recursion

Python3.3

I need to write the Hosoya's Triangle program in Python that print out the following result if we need 5 levels. The function should be recursive and follow the mentioned structure:

def computeTriangle(levels):
.
.
.
def printTriangle(triangle, levels):
.
.
.
def main():

The expected output should be exactly like this:

1

1  1

2  1  2

3  2   2  3

5  3  4  3  5

What I have tried:

I have tried this code but the output is wrong:

def computeTriangle(levels):
    if levels == 0:
        return []
    elif levels == 1:
        return [[1]]
    else:
        triangle = computeTriangle(levels-1)
        row = [1]
        for i in range(1, levels-1):
            row.append(triangle[-1][i-1] + triangle[-1][i])
        row.append(1)
        triangle.append(row)
        return triangle

# Function to print the Hosoya Triangle
def printTriangle(triangle, levels):
    for i in range(levels):
        row = [str(triangle[i][j]) for j in range(i+1)]
        print("  ".join(row))

# Main function
def main():
    
    # Compute and print the Hosoya Triangle
    levels = int(input("Enter the number of levels of the Hosoya Triangle to compute: "))
    triangle = computeTriangle(levels)
    printTriangle(triangle, levels)

if __name__ == '__main__':
    main()