4

After completing an assignment to create Pascal's triangle using an iterative function, I have attempted to recreate it using a recursive function.

I have gotten to the point where I can get it to produce the individual row corresponding to the number passed in as an argument. But several attempts to have it produce the entire triangle up to and including that row have failed. I even tried writing a separate function which iterates over the range of the input number and calls the recursive function with the iterated digit while appending the individual lines to list before returning that list. The desired output should be a list of lists where each internal list contains one row of the triangle. Like so:

[[1], [1, 1], [1, 2, 1]...]

Instead it returns a jumbled mess of a nested list completely filled with 1's.

Here is the recursive function in question, without the second function to append the rows (I really wanted one all inclusive function anyway):

def triangle(n):
    if n == 0:
        return []
    elif n == 1:
        return [1]
    else:
        new_row = [1]
        last_row = triangle(n-1)
        for i in range(len(last_row)-1):
            new_row.append(last_row[i] + last_row[i+1])
        new_row += [1]
    return new_row

To be clear, I have already completed the assigned task, this is just to provide a deeper understanding of recursion...

Iterative solution:

def triangle(n):
    result = []
    for row in range(n):
        newrow = [1]
        for col in range(1, row+1):
            newcell = newrow[col-1] * float(row+1-col)/col
            newrow.append(int(newcell))
        result.append(newrow)
    return result
Improve this question
4
  • It looks like it only returns the nth list. Is this intended? What exactly is your current output? Commented May 17, 2012 at 1:28
  • 1
    Why don't you pass a list of lists as a parameter rather than a number? Especially since the results of each row depends on the results of the previous one. Commented May 17, 2012 at 1:28
  • 1
    Can you include your iterative solution for reference? Commented May 17, 2012 at 1:28
  • @robert the intention is to output a list of lists, where each list is a row of the triangle. I got to this point, but any attempt I have made to collect the rows into a list have resulted in arbitrarily nested lists containing 1's. Commented May 17, 2012 at 1:37

5 Answers 5

Reset to default
13

You just need to pass a list of lists through the recursion, and pick off the last element of the list (i.e. the last row of the triangle) to build your new row. Like so:

def triangle(n):
    if n == 0:
        return []
    elif n == 1:
        return [[1]]
    else:
        new_row = [1]
        result = triangle(n-1)
        last_row = result[-1]
        for i in range(len(last_row)-1):
            new_row.append(last_row[i] + last_row[i+1])
        new_row += [1]
        result.append(new_row)
    return result
Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

No problem. Recursion can be confusing. I'd recommend using a lot of print statements, or a good debugger.
This still print out [1 ,1]?
how about add one more base case for n = 2 return [1, 2, 1]
4

An alternative to happydave's solution, using tail recursion:

def triangle(n, lol=None):
    if lol is None: lol = [[1]]
    if n == 1:
        return lol
    else:
        prev_row = lol[-1]
        new_row = [1] + [sum(i) for i in zip(prev_row, prev_row[1:])] + [1]
        return triangle(n - 1, lol + [new_row])
Improve this answer

2 Comments

I think it's a little clearer as [x + y for x, y in zip([0] + prev_row, prev_row + [0])].
@KarlKnechtel: I think you're right. I like the zip(a,a[1:]) trick though :)
0

Yes, as Karl Knechtel also showed, a recursive Pascal's triangle can go this way:

P=lambda h:(lambda x:x+[[x+y for x,y in zip(x[-1]+[0],[0]+x[-1])]])(P(h-1))if h>1 else[[1]]
print(P(10))
Improve this answer

Comments

0

I think it should be helpful. This code draws a triangle and does it recursively:

def traingle(n):
    if n == 1:
        print(1)
        return [1]
    else:
        answer = [1]
        print_able = '1 '
        previos = traingle(n-1)
        for index in range(len(previos)-1):
            eleman = previos[index]+previos[index+1]
            answer.append(eleman)
            print_able += str(eleman)+' '
        answer.append(1)
        print_able += '1'
        print(print_able)
        return answer


end = int(input())
traingle(end)
Improve this answer

Comments

0

Here is one. it returns a list of row lists:

def listPascal(n):
  row = [1] 
  if n == 0: return [row] # Stop condition 
  for c in range(1,n+1):  # Fill row [1,r..r,1] 
    row += [row[-1]*(n-c+1)//c]
  return listPascal(n-1) + [row] # Recurse
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.