Python Pascal's Triangle Recursion Program

Question

I'm trying to write a program to print a pascal's triangle. Here's my code:

def combination(n, k):
    if k == 0 or k == n:
        return str(1)
    else:
        return combination(str(n-1, k-1)) + combination(str(n-1,k))

def pascals_triangle(rows):
    for row in range(rows):
        answer = ""
        for column in range(row + 1):
            answer = answer + combination(row, column) + "\t"
        print(answer)

pascals_triangle(10)

This is what I was given to work with (this is for an assignment):

# To complete this assignment, replace the code for the
# combination function with the proper definition.

def combination(n, k):
    return "C(" + str(n) + "," + str(k) + ")"

def pascals_triangle(rows):
    for row in range(rows):
        answer = ""
        for column in range(row + 1):
            answer = answer + combination(row, column) + "\t"
        print(answer)

pascals_triangle(10)

It is supposed to print this:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1

I know the problem is in the combination function, but every time I try to fix something I get more errors. This currently gets me this error:

TypeError: str() argument 2 must be str, not int

I'm very much a beginner, so it's likely I'm missing some other stuff too. Can I have help fixing this error and anything else I'm missing?

Answer 1

Your immediate problem is this line:

return combination(str(n-1, k-1)) + combination(str(n-1,k))

Assuming you want to preserve most of your existing logic, the simplest fix is to instead do:

return str(int(combination(n - 1, k - 1)) + int(combination(n - 1, k)))

Complete code:

def combination(n, k):
    if k == 0 or k == n:
        return str(1)
    else:
        return str(int(combination(n - 1, k - 1)) + int(combination(n - 1, k)))

def pascals_triangle(rows):
    for row in range(rows):
        answer = ""

        for column in range(row + 1):
            answer += combination(row, column) + " "

        print(answer)

pascals_triangle(10)

OUTPUT

1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 
1 5 10 10 5 1 
1 6 15 20 15 6 1 
1 7 21 35 35 21 7 1 
1 8 28 56 70 56 28 8 1 
1 9 36 84 126 126 84 36 9 1 

A better approach is to realize that you don't need recursion, nor the combination() function, but instead recompute the line right to left:

def pascals_triangle(rows):
    answer = []

    for row in range(rows):
        answer.append(1)  # both widen the row and initialize last element

        for i in range(row - 1, 0, -1):  # fill in the row, right to left
            answer[i] += answer[i - 1]  # current computed from previous

        print(*answer)

OUTPUT

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1