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

短命女 2021-11-26 11:02 484阅读 0赞

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

递归函数：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA3MDQ3Mw_size_16_color_FFFFFF_t_70][]

算法设计思想：

第一步：为递归函数设计一个结构体(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。

![20190724001457980.png][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA3MDQ3Mw_size_16_color_FFFFFF_t_70]: /images/20211126/f4e239a3653d43c79010fadb3ee21479.png
[20190724001457980.png]: /images/20211126/835944a0b2964b48a0a2770253caf6ff.png