Geek asks and answers

Recursive pascal triangle

After completing a task to create a pascal triangle using an iterative function, I tried to recreate it using a recursive function. I went so far as to make him create a separate line corresponding to the number passed as an argument. But several attempts to get him to create the entire triangle down to this line, including this line, failed. I even tried writing a separate function that iterates over the range of the input number and calls a recursive function with a repeated digit, adding separate lines for the list before returning this list. The desired result should be a list in which each internal list contains one line of the triangle. For instance:

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

Instead, it returns the messy mess of the nested list, completely populated with 1st.

Here is the recursive function in question, without a second function to add rows (I still need 1 all-encompassing function):

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 for 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
+3
source share
2 answers

You just need to pass the list of lists through recursion and select the last element of the list (i.e. the last line of the triangle) to create a new line. For instance:

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
+11
source

Alternative to happydave 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])
+4
source

More articles:


All Articles