hosoya triangle originally fibonacci triangle is a triangular arrangement of numbers where if you take any number it is the sum of 2 numbers above first line is always 1 and second line is always 1 1 this printhosoya function takes argument n which is the height of the triangle number of lines for example printhosoya 6 would return 1 1 1 2 1 2 3 2 2 3 5 3 4 3 5 8 5 6 6 5 8 the complexity is on3 calculates the hosoya triangle height height of the triangle prints the hosoya triangle height height of the triangle test hosoya function height height of the triangle calculates the hosoya triangle height height of the triangle prints the hosoya triangle height height of the triangle test hosoya function height height of the triangle
def hosoya(height, width):
    
    if (width == 0) and (height in (0,1)):
        return 1
    if (width == 1) and (height in (1,2)):
        return 1
    if height > width:
        return hosoya(height - 1, width) + hosoya(height - 2, width)
    if width == height:
        return hosoya(height - 1, width - 1) + hosoya(height - 2, width - 2)
    return 0

def print_hosoya(height):
    
    for i in range(height):
        for j in range(i + 1):
            print(hosoya(i, j) , end = " ")
        print ("\n", end = "")

def hosoya_testing(height):
    
    res = []
    for i in range(height):
        for j in range(i + 1):
            res.append(hosoya(i, j))
    return res