利用栈实现递归函数的非递归计算（非递归求阶乘）_利用栈实现递归函数的非递归算法

递归程序在执行时需要系统提供隐式栈这种数据结构来头现，对于一般的递归过程，仿照递归算法执行过程中递归工作栈的状态变化可直接写出相应的非递归算法，利用栈消除递归过程的步骤如下。
(1）设置一个工作栈存放递归工作记录（包括实参、返回地址及局部变量等。

(2）进人非递归调用入口（即被调用程序开始处）将调用程序传来的实在参数和返回地址人栈
(3）进人递归调用入口：当不满足递归结束条件时，逐层递归，将实参、返回地址及局部变量入栈，这一过程可用循环语句来实现（模拟递归分解的过程）。
(4）递归结束条件满足，将到达递归出口的给定常数作为当前的函数值（模拟递归结束）。
(5）返回处理：在栈不空的情况下，反复退出栈顶记录，根据记录中的返回地址进行题意规定的操作，即逐层计算当前的数值，直全栈空为止（模拟递归求值过程）。
        通过以上步骤，可将任何何递归算法改与成非递归算法。但改与后的非递归算法和原来比较起来，结构不够清晰，可读性差，有的还需要经过一系列的优化。

---

例：利用栈实现非递归方式来计算递归函数：

F(n) = F(n-1)*n          n>1;

        =  1                    n=1;

先来分析一下阶乘的实现过程，需要一个隐形的栈进行控制：

初始输入n=3，由于n大于1，不满足结束条件，将n=3进行存储表示F(3)未计算

计算n=n-1，n=2>1，不满足结束条件，将n=2进行存储表示F(2)未计算

计算n=n-1，n=1，满足结束条件，F(1)=1完成计算

取出存储区域的2，并计算F(2)=F(1)*2=2

取出存储区域的3，并计算F(3)=F(2)*3=6

此时工作记录为空，计算完毕返回结果6

可见，计算阶乘时数据具有先进后出的特点，因此采用栈来实现其非递归过程

思路：（1）当n>1时重复执行将n压栈，然后n=n-1；

            （2）当n=1时，记录F=1(对应于F(1)=1)；

            （3）重复执行当栈不为空时出栈，设栈顶元素为e，则更新：F=F*e；

#include <iostream>
using namespace std;
#define ERROR 0;
#define OK 1;
typedef int Status;
 
//定义链栈
typedef struct StackNode {
	int data;
	struct StackNode *next;
} StackNode, *LinkStack;
 
//初始化栈
Status InitStack(LinkStack &S) {
	S = NULL;
	return OK;
}
 
//判断栈是否为空
int IsEmptyStack(LinkStack S) {
	if (S == NULL)
		return 1;
	else
		return 0;
}
 
//入栈
Status Push(LinkStack &S, int e) {
	StackNode *p = new StackNode;
	p->data = e;
	p->next = S;
	S = p;
	return OK;
}
 
//出栈
Status Pop(LinkStack &S, int &e) {
	if (S == NULL)
		return ERROR;
	e = S->data;
	StackNode *p = S;
	S = S->next;
	delete p;
	return OK;
}
 
int main () {
	int n, e;
	int F = 1;
	cin >> n;
	LinkStack S;
	InitStack(S);
	cout << "F(" << n << ")=";
	while (n) {            //当n>1时重复执行将n压栈，然后n=n-1；
		Push(S, n);
		n--;
	}
	while (!IsEmptyStack(S)) {
		Pop(S, e);
		if (n == 1)      
			F = 1;         //当n=1时，记录F=1
		else
			F = F * e;     //重复执行当栈不为空时出栈，设栈顶元素为e，则更新：F=F*e
	}
	cout << F;
	return 0;
}

运行结果如下：