【正确答案】递归算法可以根据函数的定义来编写。 float Legendre_(float x,int n) { if(n==0) return 1; if(n==1) return x; return ((2*n-1)*x*Legendre(x,n-1)-(n-1)*Legendre(x,n-2))/n; }

【正确答案】使用迭代法的非递归算法：从多项式的定义中可以看出，要求Legendre(x,n)，必须先求Legendre(x,n-1)和Legendre(x,n-2)，递归结束于Legendre(x,0)和Legendre(x,1)。只要用backone保存Legendre(x,n-1)，用backtwo保存Legendre(x,n-2)，即可求Legendre(x,n)。不需要使用栈编写非递归算法。用这种思路编写的非递归算法代码如下： float Legendre(float x,int n) { float current,backone,backtwo; int i; if(n==0) return 1; if(n==1) return x; backone=x;backtwo=1; for(i=2;i＜=n; ++i) { current=((2*n-1)*x*backone-(n-1)*backtwo)/n; backtwo=backone; backone=current; } return current; }