list of polynomial functions

[Matteo]

Josiah Manson wrote:
> In the following program I am trying to learn how to use functional
> programming aspects of python, but the following program will crash,
> claiming that the recursion depth is too great. I am attempting to make
> a list of polynomial functions such that poly[0](3) = 1, poly[1](3) =
> 3, poly[2](3) = 9, etc. Could someone point me in the right direction?
> Thanks.
>
> def make_polys(n):
> 	"""Make a list of polynomial functions up to order n.
> 	"""
> 	p = lambda x: 1
> 	polys = [p]
>
> 	for i in range(n):
> 		polys.append(lambda x: polys[i](x)*x)
>
> 	return polys
>
> # construct a vector of polynomials
> polys = make_polys(5)
>
> # print
> for p in polys:
> 	print p(3)

Many wise things have been said in this thread. I would like to proffer
another solution which does not rely on default arguments, just for a
more functional flavor.

def makepolys(n):
  if n==0:
    return [lambda x: 1]
  else:
    tailfunc=makepolys(n-1)
    return tailfunc + [ lambda x: x * tailfunc[-1](x)]

Another way, which is properly tail recursive is the following:

def makepolys2helper(n,retval):
  if n==0:
    return retval
  else:
    return makepolys2helper(n-1,retval+[lambda x: x* retval[-1](x)])

def makepolys2(n):
  return makepolys2helper(n,[lambda x: 1])

(Note: this could be collapsed into a single function either with a
default argument, or a nested function, but I thought this was a bit
clearer)

This last approach could, at least theoretically, create an arbitrarily
long list of polys, without overflowing any kind of stack. In practice,
python does not seem to perform tail recursion optimizations, and conks
out after makepolys(997) on my machine.

And yes - I did just sit in on my first functional programming class :)

-matt