def gray_code(n):
    if n == 0:
        return ["0"]
    if n == 1:
        return ["0", "1"]

    prev = gray_code(n-1)
    result = []
    for s in prev:
        ____________________________
    for i in range(len(prev)-1, -1, -1):
        result.append("1" + prev[i])
    return result