2
\$\begingroup\$

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 > 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)
\$\endgroup\$
  • \$\begingroup\$ I would recommend reading accepted answers and accepting an answer. It's not required, but it's a nice way to show appreciation for those who have helped you. You might also consider going back to your older question and accepting an answer there. \$\endgroup\$ – Graham Nov 16 '18 at 12:28
  • \$\begingroup\$ Thanks for the feedback, you both made very good points. I have a lot to digest. \$\endgroup\$ – d_darric Nov 16 '18 at 14:44
2
\$\begingroup\$

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 > 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 > 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 < 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]  -> [ 1, 3, 3, 1, 0 ]

  prev[1:]  -> [ 3, 3, 1, 0 ]
+ prev[:-1] -> [ 1, 3, 3, 1 ]
-----------------------------
         [1] + [ 4, 6, 4, 1 ]

This gives the correct generation of the first row: calculate([]) --> [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 & 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
\$\endgroup\$
  • \$\begingroup\$ I agree that what I am doing is disguising iteration as recursion and the iterative approach makes more sense. But I am trying to exercise recursion right now so I can move on from the topic and be confident I now how it "works". \$\endgroup\$ – d_darric Nov 17 '18 at 14:56
  • \$\begingroup\$ Try the Tower of Hanoi problem. While there is an iterative solution to that puzzle, it is actually more complex (requires figuring out which move is valid) than the recursive solution (shorter code, requires no decisions). \$\endgroup\$ – AJNeufeld Nov 17 '18 at 16:40
  • \$\begingroup\$ I tried this one not so long ago it was out of my grasp, I will keep improving and then circle back to it. Thanks for the advice. \$\endgroup\$ – d_darric Nov 22 '18 at 8:45
2
\$\begingroup\$

RecPascal feedback

PEP-8, the widely-accepted style guide for Python, advises the following:

Function and Variable Names

Function names should be lowercase, with words separated by underscores as necessary to improve readability.

Variable names follow the same convention as function names.

mixedCase is allowed only in contexts where that's already the prevailing style (e.g. threading.py), to retain backwards compatibility.

So you will probably want to rename this function to rec_pascal(). I would also recommend generally familiarizing yourself with PEP-8's guidelines; it makes it easier to communicate code with other Python users.


[] as a default function parameter is a red flag because mutable default function arguments are modified outside of the function's scope:

def RecPascal(n, m=1, prev=[]):

This is unlikely to cause problems in your current code (although it could if people do nonstandard calls), but it's better to be safe than sorry. The common workaround is to make the parameter default None, and then replace it with an empty list if it's None:

def RecPascal(n, m=1, prev=None):
    if prev is None:
        prev = []

I don't like your m parameter (though if I could indulge in a conceptual suggestion, you can fix your n+1 iterations problem by initializing m to 0; then you just compare m to n.) The m parameter is somewhat unintuitive and also unnecessary because you can glean the same information for the length of prev. But more importantly it comes from an iterative mindset; you're using it as a counter to compare to the total (which is n).

Not to say iteration is bad, but it's cleaner to do it inline (instead of as a counter parameter for a recursive function) if you're going to do it iteratively:

def RecPascal(n):
    triangle = [[1], *([None] * (n-1))]
    for i in range(1, n): 
        triangle[i] = calculate(triangle[i-1])

I will come back to a better way to do it recursively.

calculate feedback

Python has a fancy way of extending assignment. Instead of res[0], res[-1] = 1, 1, you can do res[0] = res[1] = 1. It's mostly a matter of personal style (though it can be convenient and it looks a bit cleaner.)


This loop can be structured better:

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

Since you already know only the first and last elements are 1, you don't have to iterate through them or check for elements equal to 1. Instead, you can just restrict your range more tightly:

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

And... AJNeufeld basically said was what I was going to say about refactoring it to be a better recursive function (with slight variation, maybe even a bit better than I would have done it). I'll let that answer take it from here.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.