function giving different result with @functool.cache

[naughtysensei]

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 listo

so 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?

[deanhystad]

The problem is that nextrow() modifies prerow. The problem happens here.

return pascal_re(n - 1) + [nextrow(pascal_re(n - 1)[-1])]
#      ^ a                         ^ b

Without the cache, a and b are different lists, so changing b[-1] does not affect a. With the cache, a and b are the same list, so changing b[-1] changes a[-1]. To fix the problem you need to make all your modifications in nextrow happen to a different list.

@functools.cache
def pascal_re(n):
    def nextrow(prerow):
        '''gives next row of pascal's triangle from previous row'''
        prerow = [1].append(prerow)  # Makes a new list.  Fixes shared list problem.
        for i in range(1, len(prerow) - 1):
            prerow[i] += prerow[i+1]
        return prerow
 
    if n == 1:
        return [[1]]
    return pascal_re(n - 1) + [nextrow(pascal_re(n - 1)[-1])]

[deanhystad]

You can also make recursion a lot faster by using less of it.

def pascal_re(n):
    def nextrow(r):
        '''gives next row of pascal's triangle from previous row'''
        prerow = [1].append(prerow)  # Makes a new list.  Fixes shared list problem.
        for i in range(1, len(prerow) - 1):
            prerow[i] += prerow[i+1]
        return prerow

    if n == 1:
        return [[1]]
    tmp = pascal_re(n - 1)  # Compute once and use twice
    return tmp + [nextrow(tmp[-1])]
 
print(pascal_re(25))

[naughtysensei]

        prerow = [1].append(prerow)  # Makes a new list.  Fixes shared list problem.
        for i in range(1, len(prerow) - 1):
            prerow[i] += prerow[i+1]
        return prerow

you mean this:

one = [1]
one.extend(prerow)
prerow = one
for i in range(1, len(prerow)-1):
    prerow[i] += prerow[i+1]
return prerow

or even better I guess:

prerow = prerow.copy()
for i in range(len(prerow)-1):
    prerow[i] += prerow[i+1]
return [1] + prerow

It is now obvious where I fucked up. thx. "Make a new list" this helped.