Getting Pascal's triangle recursively in Python I've been practicing recursion lately and wrote this code to get Pascal's triangle recursively.

How would you guys improve it ?

I don't really like the fact that the recursion goes for n+1 steps.

def RecPascal(n, m=1, prev=[]):
    if m &gt; n+1:
        return []
    elif m == 1:
        return RecPascal(n, m+1 , [1])
    else:
        return [prev] + RecPascal(n, m+1, calculate(prev))

def calculate(prev):
    res = [0]*(len(prev)+1)
    res[0], res[-1] = 1, 1
    for i in range(0,len(res)):
        if res[i] == 0:
            res[i] = prev[i-1] + prev[i]
    return res

for line in RecPascal(10):
    print(line)
Similar to your Water Jug solution, this is still not a good recursive algorithm/implementation.  But we can still critic it, and provide useful feedback.

First, the default argument m=1 is awkward, which leads to the odd if m &gt; n+1: and if m == 1: test conditions.  Changing the default argument to zero reduces this oddness:

def RecPascal(n, m=0, prev=[]):
    if m &gt; n:
        return []
    elif m == 0:
        return RecPascal(n, m+1 , [1])
    else:
        return [prev] + RecPascal(n, m+1, calculate(prev))


The elif m == 0: case seems to exist only to seed the algorithm with the first row of Pascal's Triangle.  The default value prev=[] is never used the code; if only one parameter is given, the second value's default causes return RecPascal(n, m+1, [1]) to be executed and prev is not used.  If you instead use [1] as the default value, you can eliminate the n+1-th recursive step.

def RecPascal(n, m=0, prev=[1]):
    if m &lt; n:
        return [prev] + RecPascal(n, m+1, calculate(prev))
    return []


A bit of inspection will reveal that this is (like the Water Jug solution) just a loop disguised as recursion; it can be rewritten without recursion as:

def RecPascal(n):
    triangle = []
    row = []
    for _ in range(n):
        row = calculate(row)
        triangle.append(row)
    return triangle




In the calculate(prev) helper function, you initialize res to a row of zeros, and then fill in the end values with 1:

    res = [0]*(len(prev)+1)
    res[0], res[-1] = 1, 1


You could replace this with initializing res with a row of ones:

    res = [1] * (len(prev)+1)


Of course, then you can't look for the res[i] == 0 values to fill in, but we don't need to look, we know the exact indices that need filling in:

    for i in range(1, len(res)-1):
        res[i] = prev[i-1] + prev[i]


This gives a much cleaner helper function.  We can even get rid of a -1 by using using the len(prev) instead of len(res):

def calculate(prev):
    res = [1] * (len(prev)+1)
    for i in range(1, len(prev)):
        res[i] = prev[i-1] + prev[i]
    return res


If we wanted to be tricky, we could add a 0 to the end of prev, and then add corresponding elements of two slices of the prev list together, and prepend a 1 to the beginning:

def calculate(prev):
    prev = prev + [0]
    return [1] + [x+y for x,y in zip(prev[1:], prev[:-1])]


Which works like this:

prev + [0]  -&gt; [ 1, 3, 3, 1, 0 ]

  prev[1:]  -&gt; [ 3, 3, 1, 0 ]
+ prev[:-1] -&gt; [ 1, 3, 3, 1 ]
-----------------------------
         [1] + [ 4, 6, 4, 1 ]


This gives the correct generation of the first row: calculate([]) --&gt; [1].  If we added 0 to both the start and back, we'd correctly calculate the 1's at each end (0+1 = 1, and 1+0 = 1) but would have to seed the first row with [1].

Since calculate is a helper for RecPascal, and won't be used anywhere else, you can "hide" it by moving it inside of RecPascal, shown here with the alternate calculation (prepending &amp; appending 0's, seeding first row as [1]) method:

def RecPascal(n):

    def calculate(prev):
        prev = [0] + prev + [0]
        return [x+y for x,y in zip(prev[1:], prev[:-1])]

    triangle = []
    row = [1]
    for _ in range(n):
        triangle.append(row)
        row = calculate(row)

    return triangle