Nov-23-2020, 12:18 PM
I wrote this code to give first 'n' rows for pascal's triangle:
def pascal_re(n): def nextrow(prerow): '''gives next row of pascal's triangle from previous row''' for i in range(len(prerow) - 1): prerow[i] += prerow[i+1] return [1] + prerow if n == 1: return [[1]] return pascal_re(n - 1) + [nextrow(pascal_re(n - 1)[-1])] print(pascal_re(5))
Output:[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
but the output was quite slow (say for n=25) compared to my iterative version for same:def pascal_it(n): listo = [] for i in range(n): lst = [1] for j in range(i-1): lst.append(listo[i-1][j] + listo[i-1][j+1]) if i: lst.append(1) listo.append(lst) return listoso I used @functools.cache:
import timeit @functools.cache def pascal_re(n): def nextrow(prerow): '''gives next row of pascal's triangle from previous row''' for i in range(len(prerow) - 1): prerow[i] += prerow[i+1] return [1] + prerow if n == 1: return [[1]] return pascal_re(n - 1) + [nextrow(pascal_re(n - 1)[-1])] print(pascal_re(5))
Output:[[1], [2, 1], [3, 3, 1], [4, 6, 4, 1], [1, 4, 6, 4, 1]]
the output is different from before, what is going on here, how can I make my recursive version faster and right?