2
\$\begingroup\$

I wrote this code for Pascal's Triangle using recursion. Can someone please help me to review it for better performance?

# argument count is number of rows which is entered from terminal.
def pascal_t(count,input_list=0):

    if not count: exit() # if count is 0 program will exit.

    if not input_list: # to print first element as 1 when there is no input list.
        created_array=[1]
        print (count*"   "),"    ".join(map(str,created_array))

        pascal_t((count-1),created_array) # recursive call; created array will be taken as input list.

    created_array=[] # initializing list

    # for loop to insert numbers in created_array
    for index in range(len(input_list)):
        if not index: # when index is 0 then first value will be inserted in created_ array
            if (index+1)==len(input_list): # if there is only 1 element in the list, this condition will insert first element again in created_array
                created_array.append(input_list[index])
            created_array.append(input_list[index])

        elif (index+1)==len(input_list):    # when index is second last, it will insert two elements in created_array       
            created_array.extend((input_list[index-1]+input_list[index],input_list[index]))

        else:
            created_array.append(input_list[index-1]+input_list[index])

    # list formatting for proper pattern printing.
    formatted_list = [str(num)+"   " if num>9 and num<=99 else str(num)+"  " if num>99 and num<=999 else str(num)+" " if num>999 and num<=9999 else str(num)+"" if num>9999 else str(num)+"    " for num in created_array]

    # Creating and printing string from created_array   
    string_to_print = " ".join(formatted_list)
    print count*"   ",string_to_print
    pascal_t((count-1),created_array) # recursive call; created array will be taken as input list.

# function call with user input from terminal
pascal_t(int(raw_input("Enter Number of Rows(1-20) for Pascal's Triangle: ")))
\$\endgroup\$
  • \$\begingroup\$ Are you only limited to use recursion? if not you will get better performance using binomial coefficients. \$\endgroup\$ – Alex Jan 30 '17 at 11:29
  • \$\begingroup\$ @Alex, nope, no limitation. However, I am not much into binomials so please can you suggest how may I use it with this code? \$\endgroup\$ – Shubham Namdeo Jan 30 '17 at 11:57
2
\$\begingroup\$

Someone already commented about not using recursion but if you still want to keep it, here are my comments.

There are quite a few style issues, if you install the pep8 command and run from the command line pep8 pascal.py (or whatever the filename is), you'll see them (multiple statements on one line, missing whitespace around operator, line too long).

Other than that, a few things:

  • I'd definitely check that the input is a number, you don't want to feed letters or other characters to your function.
  • The input_list parameter should be initialized properly. It's supposed to be a list, not an integer. But since it's not nice to initialize it to [], you can set it to None and check on that. (For an explanation why this is not nice, you can have a quick look here)
  • Your function name is pascal_t, to me that looks like it returns a pascal triangle, while it actually prints it. I'd say either rename it to print_pascal_t or make it return an object and print that.
  • A lot of comments. You can remove quite a few of them just by giving proper names. For example, count can be renamed to rows_number and you can remove the first line. You can be more explicit with the first check (if rows_number <= 0: ) and remove that comment, too. The other comments are simply describing what happens. I think good comment should be describing why things happen, otherwise it's either useless, or you need to write code more clearly.
  • The first check on if not index is useless, you can remove that part of code.
  • You also don't need to create an array with a single element so that you can map, cast and join it.
  • You exit() the program inside of your function instead of just returning. I'd check if input_list is None and just return in that case.
  • The formatting line can be converted to something much simpler using, well, format :-)
  • Just as a side note, this will not work properly in python3.

Modified code:

def pascal_t(rows_number, input_list = None):
    if rows_number <= 0:
        return

    if not input_list:
        print(rows_number * "   "), "1"
        pascal_t((rows_number - 1), [1])
        return

    created_array = []

    for index in range(len(input_list)):
        if (index + 1) == len(input_list):
            created_array.extend((input_list[index - 1] + input_list[index], input_list[index]))
        else:
            created_array.append(input_list[index - 1] + input_list[index])

    formatted_list = ['{0: <5}'.format(str(num)) for num in created_array]

    print rows_number * "   ", " ".join(formatted_list)
    pascal_t((rows_number - 1), created_array)

user_input = raw_input("Enter Number of Rows(1-20) for Pascal's Triangle: ")
try:
    rows_number = int(user_input)
except ValueError:
    print "Not a valid number"
else:
    pascal_t(rows_number)
\$\endgroup\$
  • \$\begingroup\$ good one, I didn't spend that much time to review existing code but suggest a better solution. If author still going to keep recursion your code cleanup is definitely better than mine. \$\endgroup\$ – Alex Jan 30 '17 at 15:20
1
\$\begingroup\$

Alright, if we are not only limited to recursion, then I would go for something like this:

from math import factorial

def print_triangle(height):

    triangle = ([factorial(n) // (factorial(k) * factorial(n - k)) for k in range(n+1)]
                for n in range(height))

    for i, line in enumerate(triangle):
        offset = height - i
        string_to_print = ' '.join((str(num)+"    ")[:6] if number <100000 else str(num) for num in line)
        print offset * "   ", string_to_print

However if you want to make your code more readable then there are few things you should do.

1.Please read and follow python style guide PEP8

2.This hard to read line:

formatted_list = [str(num)+"   " if num>9 and num<=99 else str(num)+"  " if num>99 and num<=999 else str(num)+" " if num>999 and num<=9999 else str(num)+"" if num>9999 else str(num)+"    " for num in created_array]

Can be simplified to:

formatted_list = [(str(num)+"    ")[:6] if number <100000 else str(num) for num in created_array]

Now here:

def pascal_t(count,input_list=0):

Its' better to use either None for input_list default value or empty tuple.

Also this:

    if not count:
        exit()  # if count is 0 program will exit.

Well, I'd prefer to function just quit, e.g empty return and do your sys.exit somewhere in the main block. So in future, you would be able to use your print triangle function without making your program to shutdown.

\$\endgroup\$
  • \$\begingroup\$ (str(num)+"    ")[-6:] is surely not right! Try it with num=123456 and you get "56    ". I think that the expression you are looking for is format(num, '<6'). \$\endgroup\$ – Gareth Rees Jan 30 '17 at 12:52
  • \$\begingroup\$ @GarethRees thanks, missed this one, it should be (str(num)+" ")[:6] if number <100000 else str(num) \$\endgroup\$ – Alex Jan 30 '17 at 13:08
  • 2
    \$\begingroup\$ [factorial(n) // (factorial(k) * factorial(n - k)) for k in range(n+1)] is doing a lot of wasted work. If each element in the row is calculated from the previous one then there's an asymptotic improvement by a factor of n. \$\endgroup\$ – Peter Taylor Jan 30 '17 at 15:32
  • 1
    \$\begingroup\$ @PeterTaylor well yes and no, it will work faster on small triangles up to ~50 height and will be slower on bigger ones. But you can optimize it if you need to render bigger ones faster if that is a case. However, I think that readability with binomial coefficients is much better than with recursion \$\endgroup\$ – Alex Jan 30 '17 at 15:42

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.