如何把递归函数变成非递归的，一般是什么思路？？
如何把递归函数变成非递归的，一般是什么思路？？
例如
f(n)=n+1 if n=1 or i=2
f(n-1)*f(n-2)+1 if n=3,4,...
问题点数：20、回复次数：5Top
1 楼cutepig123（）回复于 2006-03-20 01:30:09 得分 0
要求用堆栈实现
比如这一个
或者
f(m,n)=n+1 if m=0
f(m-1,n) if n=0
f(m-1,f(m,n-1)) if m!=0 and n!=0Top
2 楼cutepig123（）回复于 2006-03-20 02:06:13 得分 0
#include <stdio.h> 憶蜳?j轻M
#define MAXN 8000 ?酈5紮PI
typedef struct node{ ?gl@ 剺k?
int n; ??i<"餧
double x,y; 2 lL &K
}NODE; 扉?b泄_筣
NODE stack[NAXN]; )岝2
int top,deb,depth; 个LBB?l?
鋾"]?仵
int push(NODE stack[],int maxn,int *toppt,NODE x） /*进栈函数*/ 螤Tf6S` 鈅
{ ?P騛巇刐?
if(*toppt>=maxn) -?8鈞6鉓S0
return 1 /*栈满*/ G栤輒l徛?
stack[*toppt]=x; W?轗袠?
++*toppt; 挑惀夭昄I
if(*toppt>depth)depth=*toppt; bb摸?頥
return 0; /*进栈成功，返回0*/ 栫*窰D?5
} ??HMW豾/
粎f 肦v2
int pop(NODE stack[],int *toppt,NODE *cp) /*出栈函数*/ 瑉↙倛nzn?
{ ????"
if(*toppt==0)return 1; 嶫椔淿铃
--*toppt; 鈐6tRX?kI
*cp=stack[*toppt]; 戏? (+1?
return 0; o埧Mеn:
} 2尉{xnC逛
w鎚y鲾I廰
double A(NODE node) <檰$_穳€?
{ 0?lt;瓒g矞|
int k;double B; t狹芺)憝鏴
NODE tnode; 飵 纈檳腍U
top=0; depth=0; sm=+.>5嬓
push(stack,MAXN,&top,node); 鑃f7?[場#
do{ G旲骐椡榾?
tnode=stack[top-1]; /*读栈顶结点的值存入tnode*/ ~Ⅰ曄妥?N
while(tnode.n!=0&&tnode.y!=0){ ∏馰?lx/
stack[top-1].n--;stack[top-1].y=stack[top-1].x; ?仔A湕坘
stack[top-1].x=-1.0; +敼蘤屠艎
tnode.y-=1.0; ?b瑗缳鐞
if(push(stack,MAXN,&top,tnode)) /*将tnode进栈*/ ?@?填
return -1.0; ?mkD
} 捿&銅硇-?
pop(stack,&top,&tnode); ?9祗D?
/*计算：B=A(tnode)*/ 郈儙】_{
if(tnode.n==0) B=tnode.x+1.0; }p{Tm6@P(€
else if(tnode.n==1) B=tnode.x; 鞰?瘥栭帪
else if(tnode.n==2) B=0.0; ;? ?3Y?
else if(tnode.n==3) B=1.0; ???R糹?
else B=2.0; 1劤€蠒??
if(top) |翵iMwO/#~
stack[top-1].x=B; /*栈非空将栈顶结点的x值该为B*/ 怇?I僦
}while(top); ? ?:?`
return B; 曠w?譁翣?
} RzC?lt;{ s
輙鑍s=架﹩
void main() 0g]?q尴
{ 莮?gW嘙拱
NODE node={3,1,2}; ? %泜蔣 u
printf("A(3,1,2)=%f",A(node)); 纻"}?-??
} 2?n ZyF浲?
Top
3 楼xiaocai0001（高楼目尽欲黄昏/梧桐叶上萧萧雨）回复于 2006-03-20 12:42:00 得分 5
一般借助栈来实现, 递归调用, 在系统中实际上存在一个函数调用栈, 现在就要手动用自己的栈去代替系统的调用栈, 完成递归算法.Top
4 楼yelling（Ray（←☆→射手））回复于 2006-03-20 14:47:06 得分 5
有些简单情况可以推出公式改成递推
复杂点的话可以写成回溯，就是手动维护栈的方法，不过写起来麻烦一点
如果实在没办法就想办法将递归的中间结果存下来，好像这样又叫记忆搜索
Top
5 楼cutepig2（）回复于 2006-03-20 18:30:12 得分 10
把递归函数转换成非递归程序的一般方法
● 递归函数的原理
用栈保存未完成的工作，在适当的时候从栈中取出并执行。
系统保存了工作的数据和状态，数据就是函数的局部变量，
状态就是程序指针。
● 非递归程序原理
1. 和递归函数的原理相同，只不过是把由系统负责保存工作
信息变为程序自己保存，这样能减少保存数据的冗余(主要是
节省了局部变量的空间)，提高存储效率。
2. 把程序要完成的工作分成两类：手头工作和保存在栈中的
待完成的工作。手头工作指程序正在做的工作。由于某些工作
不能一步完成，必须暂缓完成，于是可把它保存在栈中，这就
是待完成的工作。
3. 手头工作必须有其结束条件，不能永远做下去；保存的
待完成工作必须含有完成该项工作的所有必要信息。
4. 程序必须有秩序地完成各项工作。如，可把手头工作恰当
处理（直接处理或暂时保存）后，才能继续接手下一步的工作。
5. 待完成工作必须转换成手头工作才能处理。
● 栈的大小
所有递归问题，其递归过程可以展开成一棵树，叶子节点是
可解的，按照问题的要求，处理所有叶子节点，就可解决
问题本身。可能需要保存(Data, Status)，Data是工作数据，
Status是工作状态；（Data, Status）决定了整个工作。
栈的大小等于树的高度-1，-1是因为根节点不需保存。
● 举例
例1. 汉诺塔问题
递归函数：
void Hanoi(UINT x, UINT y, UINT n)
// x Source
// y Destination
// n Number of plates
{
if (n == 0) return;
Hanoi(x, x^y, n-1);
Move(x, y);
Hanoi(x^y, y, n-1);
}
说明：x、y可取1、2、3三数之一，并且x≠y，x^y表示x、y按位异或，
得到除x、y之外的第三个数。1^2=3, 1^3=2, 2^3=1
非递归程序：
#define N 5
tyepdef struct _HANOIDATA
{
UINT x;
UINT y;
UINT n;
}HANOIDATA;
void Hanoi(HANOIDATA hanoiData)
{
HANOIDATA stack[N];
int top = -1; // stack pointer
while (hanoiData.n || top != -1) // 存在手头工作或待完成工作
{
while (hanoiData.n) // 处理手头工作直到无现成的手头工作，
// 即下次的手头工作必须从栈中取得
{
hanoiData.n --;
stack[++top] = hanoiData; // 保存待完成工作
hanoiData.y ^= hanoiData.x; // 新的手头工作
}
if (top != -1) // 存在待完成工作
{
hanoiData = stack[top--]; // 从栈中取出
Move(hanoiData.x, hanoiData.y); // 直接处理
hanoiData.x ^= hanoiData.y; // 未处理完的转换成手头工作
}
}
}
例2． 后根序遍历二叉树
递归函数：
void PostTraverse(BINARYTREE root)
{
if (root == NULL) return;
PostTraverse(root->LChild);
PostTraverse(root->RChild);
Visit(root);
}
非递归程序：
void PostTraverse(BINARYTREE p)
{
while ( p != NULL || !Stack.IsEmpty() )// 存在工作(手头或待完成)
{
while (p != NULL) // 处理手头工作，直到无现成手头工作
{
Stack.Push(p, RCHILD_AND_ITSELF);
p = p->LChild;
}
if (!Stack.IsEmpty()) // 是否存在待完成工作
{
Stack.Pop(p, Tag);
if (Tag == RCHILD_AND_ITSELF) // 情况一: RChild & Itself
{
Stack.Push(p, ONLY_ITSELF) // 保存待完成工作
p = p->RChild; // 新的手头工作
}
else // tag == ONLY_ITSELF, 情况二: Only Itself
{
visit(p);
p = NULL; // 已无现成的手头工作
}
}
}
}
● 总结
非递归程序的设计应注意：
1. 保存暂缓执行的工作
2. 无现成手头工作的条件
3. 无待完成工作的条件
程序模式
void NonRecursiveFunction(DATATYPE Data)
{
while ( ExistHandyWork() || ExistSavedWork() )
{
while ( ExistHandyWork() )
{
Process(Work, Status) // Probably push work onto stack
NewHandyWork();
}
if ( ExistSavedWork() )
{
Pop(Work, Status);
Process(Work, Status); // Probably generate new handy work
}
}
}
Top
