【数据结构】利用栈实现递归函数的非递归计算_利用一个栈实现以下递归函数的非递归算法

利用一个栈实现以下递归函数的非递归计算：
$$P_n(x)=\{\begin{array}{ll}1,& n=0\\ 2x,& n=1\\ 2x{P}_{n-1}(x)-2(n-1)P_{n-2}(x),& n>1\end{array}$$
我们可以设置一个栈来保存 n 和 对应的 $P_n(x)$ 的值，栈中相邻的元素 $P_n(x)$ 之间有关系 $P_n(x)=2x{P}_{n-1}(x)-2(n-1)P_{n-2}(x)$.
边出栈边计算 $P_n(x)$，栈空后该值就计算出来了。
算法的实现如下：

double p(int n,double x){
	struct stack{
		int no; //保存n
		double val; //保存 Pn(x)值
	}st[MaxSize];
	int top=-1,i; //top为栈st的下标值变量
	double fv1=1,fv2=2*x;
	for(i=n;i>=2;i--){
		top++;
		st[top].no=i;
	}
	while(top>=0){
		st[top].val=2*x*fv2-2*(st[top].no-1)*fv1;
		fv1=fv2;
		fv2=st[top].val;
		top--; //出栈
	}
	if(n==0){
		return fv1;
	}
	return fv2;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22