Proving optimized function is still correct

[Huaiyu Zhu]

On Tue, 13 Nov 2001 16:55:48 GMT, Terry Reedy <tjreedy at home.com> wrote:
>A recursive implementation like
>
>def d(m,n):   return (m == 1 or n == 0) and 1 or d(m,n-1) + d(m-1,n)
>
>is inefficient ...
[snip]

>          The following iterative solution computes each
>function value only once.
[snip]

Here is a recursive solution doing the same.  Note that m is reduced by 1 as
per usual definition of combinatorial coefficients

def dd(m, n):
	if m == 0: return [1]*(n+1)
	tmp = dd(m-1, n)
	for i in range(1, n+1):
		tmp[i] += tmp[i-1]
	return tmp

def d3(m,n):
	return dd(m, n)[-1]

The definition of dd could be moved inside d3 (using nested scope).  But it
is useful on its own.  Here's a Pascal triangle

>>> for i in range(10): print dd(i, 9-i)
... 
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 3, 6, 10, 15, 21, 28, 36]
[1, 4, 10, 20, 35, 56, 84]
[1, 5, 15, 35, 70, 126]
[1, 6, 21, 56, 126]
[1, 7, 28, 84]
[1, 8, 36]
[1, 9]
[1]

Since m and n are symmetrical, one could also compare them and choose
between space optimization vs recursion depth optimization.

Huaiyu