利用栈实现递归函数的非递归计算

题目描述：利用一个栈来实现递归函数的非递归计算。

 递归函数：

算法设计思想：

       第一步：为递归函数设计一个结构体(Func_val)用于保存函数的n和Pn(x)的值。

       第二步：定义一个栈(stack),用于保存递归函数中的n个数据(Func_val类型)。  注：栈stack保存递归函数中从2 到 n的数据 

       第三步：边出栈边计算Pn(x)的数值(出栈时n从2到n)，当栈为空时就计算出了Pn(x)的值。

算法代码：

typedef struct Func_val{
	int no;
	double val;
}Func_val;  // 为递归函数创建数据类型，方便存储
double calculate_val(int n,double x){
	Func_val *stack=(Func_val*)malloc(sizeof(Func_val)); //开辟大小为n的栈，栈中存放Func_val数据类型的值
	int top = -1;  //栈顶指针
	double f0, f1; //初始时表示n为0和1时的值
	f0 = 1;
    f1 = 2 * x;
	for (int i = n; i >=2; i--){  //递归函数n个数值依次入栈
		top++;
		stack[top].no = i;
	}
	while (top!=-1)   //边出栈边计算数值
	{
		stack[top].val = 2 * x*f1 - 2*(stack[top].no-1) * f0;
		f0 = f1;          //f0,f1保存本次中n-2和n-1项的值
		f1 = stack[top].val;
		top--;   //出栈
	}
	if (n == 0){
		return f0;
	}
	else
		return f1;   //栈空时Pn(x)值计算出来，赋值给f1
}

程序完整代码：

//递归函数非递归计算
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
typedef struct Func_val{
	int no;
	double val;
}Func_val;  // 为递归函数创建数据类型，方便存储
double calculate_val(int n,double x){
	Func_val *stack=(Func_val*)malloc(sizeof(Func_val)); //开辟大小为n的栈，栈中存放Func_val数据类型的值
	int top = -1;  //栈顶指针
	double f0, f1; //初始时表示n为0和1时的值
	f0 = 1;
    f1 = 2 * x;
	for (int i = n; i >=2; i--){  //递归函数n个数值依次入栈
		top++;
		stack[top].no = i;
	}
	while (top!=-1)   //边出栈边计算数值
	{
		stack[top].val = 2 * x*f1 - 2*(stack[top].no-1) * f0;
		f0 = f1;          //f0,f1保存本次中n-2和n-1项的值
		f1 = stack[top].val;
		top--;   //出栈
	}
	if (n == 0){
		return f0;
	}
	else
		return f1;    //栈空时Pn(x)值计算出来，赋值给f1
}
int main(){
	int n, x;
	double result;
	cout << "输入非递归函数的n,x:";
	cin >> n;
	cin >> x;
	result= calculate_val(n, x);
	cout << "\n" << "结果为：" << result;
	system("pause");
	return 0;
}

运行结果：

当n=3,x=2时，函数计算结果为40。