Recursion Pascal's Triangle (Python)

Question

I'm not sure what I'm doing wrong with my code here in getting a recursive pascal's triangle to work in python. Any help is kindly appreciated :)

n = 5
def printPascal(n):
    Pascal_List = []
    if n == 0:
        Pascal_List.append([1])
        return Pascal_List
    if n == 1:
        Pascal_List.append([1])
        Pascal_List.append([1,1])
        return Pascal_List


    else:

        new_row = [1]
        final_r = printPascal(n - 1)
        last_row = final_r[-1]
        for k in range(1, last_row[-1]):
            new_row.append(final_r[k] + final_r[k - 1])

        new_row += last_row
        final_r.append(new_row)
        return final_r

print(printPascal(n))

You need to ask about a specific problem, rather than just say "Here's my code. It doesn't work. Please debug it for me". See help center — SiHa
– SiHa, Commented May 13, 2016 at 10:34

Community · Accepted Answer · 2017-05-23 12:16:04Z

3

@zale already explained the problem with your for loop, no need to repeat that. However, note that you can make your code a good deal simpler:

no need for the special treatment of the n == 1 case
you can make the second part much simpler by padding the last line with zeros

Try this:

def printPascal(n):
    if n == 0:
        return [[1]]
    else:
        final_r = printPascal(n - 1)
        last = [0] + final_r[-1] + [0] # note: this does not modify final_r
        new_row = [last[k] + last[k - 1] for k in range(1, len(last))]
        return final_r + [new_row]

edited May 23, 2017 at 12:16

CommunityBot

11 silver badge

answered May 13, 2016 at 10:32

tobias_k

83.1k12 gold badges130 silver badges186 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

zale · Accepted Answer · 2020-06-21 03:53:17Z

1

You've made a few confusions in the loop that builds a new line. range(1, last_row[-1]) doesn't really make sense; you want to iterate over the indices of the last row, ie range(len(last_row)). You've also mixed up final_r and last_row on the next line.

Here is a corrected version of your code :

n = 5

def printPascal(n):
    Pascal_List = []
    if n == 0:
        Pascal_List.append([1])
        return Pascal_List

    if n == 1:
        Pascal_List.append([1])
        Pascal_List.append([1,1])
        return Pascal_List

    else:
        new_row = [1]
        final_r = printPascal(n - 1)
        last_row = final_r[-1]
        for k in range(len(last_row)-1):
            new_row.append(last_row[k] + last_row[k + 1])
        new_row.append(1)

        final_r.append(new_row)
        return final_r

print(printPascal(n))

edited Jun 21, 2020 at 3:53

answered May 13, 2016 at 10:24

zale

1,27912 silver badges30 bronze badges

1 Comment

Harvey Connor Over a year ago

Thank you! You're a legend :D

Moon Cheesez · Accepted Answer · 2016-05-13 10:30:06Z

1

There is a better method to do this using the general formula for Pascal's triangle (n choose k), but I will not go into that.

Looking at your code, I'm guessing you are trying to add the previous two numbers from the previous row to get the next number.

Change replace with this in your else condition:

#It should be length instead.
for k in range(1, len(last_row)):
   new_row.append(last_row[k] + last_row[k - 1])
#You need to add the 1 at the end
new_row.append(1)

edited May 13, 2016 at 10:30

answered May 13, 2016 at 10:27

Moon Cheesez

2,7213 gold badges28 silver badges41 bronze badges

Comments

Andy Richter · Accepted Answer · 2025-11-06 15:43:03Z

0

Slightly different:

n = 5
def printPascal(r):
  new_row = [1] 
  if r == 0: return [new_row] # Stop condition 
  for c in range(1,r+1):  # Fill row [1,r..r,1] 
    new_row.append(new_row[-1]*(r-c+1)//c);
  return  printPascal(r-1) + [new_row] # Recurse 
  
triangle = printPascal(n) 
M = len(" ".join(map(str,triangle[-1])))
for row in triangle: 
  print(" ".join(map(str,row)).center(M))

Output:

$ python pascal_cursed.py 
      1      
     1 1     
    1 2 1    
   1 3 3 1   
  1 4 6 4 1  
1 5 10 10 5 1

edited Nov 6 at 15:43

answered Nov 6 at 14:34

Andy Richter

3482 silver badges8 bronze badges

Collectives™ on Stack Overflow

Recursion Pascal's Triangle (Python)

4 Answers 4

Comments

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related