为什么说递归效率低？

对于递归，有人提到了两点：

（1）对栈的容量的压力。

（2）个别问题的递归解法，其算法的低效性。

这两个因素我简短点评下，

（1）对栈的容量压力：

通常递归的深度很大造成的。对于这一点当然应该有程序员编码时，来衡量和把握。win32 中一个新建的线程，默认的栈通常在 1 MB 大小。那么如果你的递归函数，深度很大，显然程序员应该对这种情况有预估，和对风险的避免。

这就和你选择，把内存分配在栈上还是堆上，会考虑到分配的内存大小的因素一样。

当然，如果在函数内分配很大的栈上空间，在函数体内定义一个很大的数组，这样不需要很深的深度，也会让栈溢出。这当然也是程序员自己应该控制的。

（2）个别问题的递归解法，算法的低效。

这个低效主要在于这个问题的算法本身。而不是在递归这种方法上。比如说求斐波那契的某一项，子问题会大量重复出现，会产生很多重复计算，这个是很多算法书上，是用来引导出动态规划或者查表法的。

这主要是算法本身的效率问题，而不是递归的问题。这一点是必须应该明确的。

（3）我们可以看到，在和树有关的算法中，经常会有递归函数。

例如，遍历文件夹，删除注册表的某一个 key （及其所有子key）。

尤其对一般树的前序，后序遍历，二叉树的中序遍历。

这主要原因是因为树的定义，就是“递归性”的：

树就是，某一个节点有多个子节点，每个子节点是一个树。

我们再此可以看到，递归的显著优点，是对解的描述的直观性，代码的简洁性。

嘿嘿，这个我做过哦。是编译原理的东西。

不过现在没有程序，没带来，给你一个参考的：虽然不是完全符合你的要求。不过其中很多函数你是要用到的，比如词法分析部分，其实你的要求就是进行词法分析的，无非你用scanf（），你用词法分析，分析出scanf（）语句，再进行内部参数分析，就OK了；

祝你成功哦

///////////////////////////////////////////////////////////////////

for循环语句翻译 递归下降法 输出三地址码 /////////////

#define MAX 100

#include<iostream.h>

#include<stdio.h>

#include<string.h>

char str[MAX]

char ch

int turn

char strToken[MAX]

int kind

int n=0//存放strtoken[]元素的个数

struct Word//结构体 存放单词

{

int sort

char word[MAX]//存放strtoken[]的内容

}

//record[x]=new Word

Word *record[12]//放所有识别出来的单词，分别存放他们的编号以及字符串，x是其下标

////////////////////词法分析///////////////////////

int buffer()//载入

{

int i=0

cout<<"输入程序，以“#”作为结束标志。"<<endl

for(int n=0n<=MAXn++)

{

for(i<=MAXi++)

{

scanf("%c",&str[i])

/////////////cin>>str[i]不可用，用C语言读入字符。

if(str[i]=='#')

break///////如果尾数为识别码#,则表示程序读完,跳出循环.

}

break

}

return(i)

}

bool IsLetter(char ch)///////////判断是否是字母

{

if(ch>=65&&ch<=90||ch>=97&&ch<=122)

return(true)

else

return(false)

}

bool IsDigit(char ch)//////////判断是否是数字

{

if(ch>=48&&ch<=57)

return(true)

else

return(false)

}

char GetChar(int i)///////读取字符

{

char ch

ch=str[i]

return(ch)

}

char GetBC(char ch)////判断是不是空格或者换行，如果是，直接读取下一个字符直道不再空白为止

{

if(ch==32||ch==10)

{

turn++

ch=GetChar(turn)

ch=GetBC(ch)/////////递归实现

return(ch)

}

else

return(ch)

}

void Concat()/////////////连接，即为strtoken[]赋值

{

strToken[n]=ch

n++

}

int Reserve()/////以单词为单位查找保留字，是则返回编码，不是则返回0，用来区分标志符和保留字

{

if(strcmp(strToken," DIM\0")==0)///////调用strcmp函数实现,

return(1)

else if(strcmp(strToken,"for\0")==0)

return(2)

else if(strcmp(strToken,"step\0")==0)

return(3)

else if(strcmp(strToken,"until\0")==0)

return(4)

else if(strcmp(strToken,"do\0")==0)

return(5)

else

return(6)

}

void clear()

{

n=0

}

/////////////*语法递归分析*/////////////////

int A(int * c,int &q)

{

if(c[q++]==3)

{

if(c[q]==7)

{ q++

return 1

}

else {cout<<"step右部出错"<<endlreturn 0}

}else {cout<<"error 'step'"<<endlreturn 0}

}

int B(int * b,int &o)

{

if(b[o++]==4)

{

if(b[o]==7)

{ o++

return 1

}

else {cout<<"until右部出错"<<endlreturn 0}

}else {cout<<"error 'until'"<<endlreturn 0}

}

int S2(int * d,int &h)

{

if(d[h++]==6)

{

if(d[h++]==8)

{

if((d[h]==6||d[h]==7)) {h++return 1}

else {cout<<"赋值语句右部出错 "<<endlreturn 0}

}else {cout<<"赋值语句缺少赋值运算符 "<<endlreturn 0}

}else {cout<<"赋值语句左部出错 "<<endlreturn 0}

}

int S1(int * m,int &n)

{

if(S2(m,n))

{

if(A(m,n))

{

if(B(m,n)) return 1

else return 0

}else return 0

}else return 0

}

int S(int *a,int &z)

{

if (a[z++]==2)

{

if (S1(a,z))

{

if(a[z++]==5)

{

if(S2(a,z))

{

cout<<"succeed!"<<endlreturn 1

}else return 0

}else {cout<<"error 'do'"<<endlreturn 0}

}else return 0

}else {cout<<"error 'for'"<<endlreturn 0}

}

void main()

{

cout<<"*************产生式***************"<<endl// for step until do i j =

cout<<" S ->for S1 do S2"<<endl// 编号 2 3 4 5 6 7 8

cout<<" S1 ->S2AB"<<endl

cout<<" S2 ->i=j"<<endl

cout<<" A ->stepj"<<endl

cout<<" B ->untilj"<<endl

int num

turn=0

num=buffer()-1

int x=0//计识别的单词的个数

for(turn<=numturn++)//总循环,ch存放刚读入的字符，strtoken[]存放已识别的标志付或保留字，turn是数组str[]的下标

{

ch=GetChar(turn)

ch=GetBC(ch)

if(IsLetter(ch))

{

while(IsLetter(ch)&&turn<=num||IsDigit(ch)&&turn<=num)

{

Concat()

ch=GetChar(++turn)

}

strToken[n]='\0'

ch=NULL//此ch不是标志符中的符号

turn=turn-1

kind=Reserve()

record[x]=new Wordrecord[x]->sort=kind//12345或6

//cout<<kind//测试

cout<<"("

for(int i=0i<ni++)

{

record[x]->word[i]=strToken[i]

cout<<record[x]->word[i]//输出识别的标志符或保留字

}

cout<<","<<kind<<")"<<endl

record[x]->word[i]='\0'

clear()

x++

}

else if(IsDigit(ch))

{

while(IsDigit(ch)&&turn<=num)

{

Concat()

ch=GetChar(++turn)

}

ch=NULL

turn=turn-1

kind=7

//////////////

record[x]=new Word

record[x]->sort=kind

////////////////

cout<<"("

for(int i=0i<ni++)

{

record[x]->word[i]=strToken[i]

cout<<record[x]->word[i]

}

cout<<","<<kind<<")"<<endl

record[x]->word[i]='\0'

clear()x++

}

else if(ch=='=')

{

kind=8

///////

record[x]=new Word

record[x]->word[0]='='

record[x++]->sort=kind

cout<<"(=,"<<kind<<")"<<endl

}

else

cout<<"error input!"<<endl

}

//////////////////////*语法分析*////////////////

//int y

/*for(y=0y<xy++)

{cout<<record[y]->sort<<" "//打印单词的编号 。

}cout<<endl*/

int ana[MAX]//存放词法分析得到的单词序列的编号的序列

int m

for(m=0m<xm++)

{

ana[m]=record[m]->sort//将sort作为数组保存起来

}

/////////语法分析///////

int j=0

///////////////////制导翻译//////////////////

if(!S(ana,j)) cout<<"语法出错!"<<endl

else

{ cout<<"三地址码如下："<<endl

cout<<"100 "

int i=0

while(record[1]->word[i]!='\0')

cout<<record[1]->word[i++]cout<<record[2]->word[0]

i=0

while(record[3]->word[i]!='\0')

cout<<record[3]->word[i++]cout<<endl

cout<<"101 goto 103"<<endl

cout<<"102 "

i=0

while(record[1]->word[i]!='\0')

cout<<record[1]->word[i++]cout<<":="

i=0

while(record[1]->word[i]!='\0')

cout<<record[1]->word[i++]cout<<"+"

i=0

while(record[5]->word[i]!='\0')

cout<<record[5]->word[i++]cout<<endl

cout<<"103 if "

i=0

while(record[1]->word[i]!='\0')

cout<<record[1]->word[i++]cout<<"<"

i=0

while(record[7]->word[i]!='\0')

cout<<record[7]->word[i++]

cout<<" goto 105"<<endl

cout<<"104 goto 107"<<endl

cout<<"105 "

i=0

while(record[9]->word[i]!='\0')

cout<<record[9]->word[i++]cout<<":="

i=0

while(record[11]->word[i]!='\0')

cout<<record[11]->word[i++]cout<<endl

cout<<"106 goto 102"<<endl

cout<<"107 end"<<endl

}

}

分成词法分析，语法分析（LL算法，递归下降算法，LR算法），语义分析，运行时环境，中间代码，代码生成，代码优化这些部分。其实现在很多编译原理的教材都是按照85,86出版的那本龙书来安排教学内容的，所以那本龙书的内容格式几乎成了现在编译原理教材的定式，包括国内的教材也是如此。一般来说，大学里面的本科教学是不可能把上面的所有部分都认真讲完的，而是比较偏重于前面几个部分。像代码优化那部分东西，就像个无底洞一样，如果要认真讲，就是单独开一个学期的课也不可能讲得清楚。所以，一般对于本科生，对词法分析和语法分析掌握要求就相对要高一点了。

词法分析相对来说比较简单。可能是词法分析程序本身实现起来很简单吧，很多没有学过编译原理的人也同样可以写出各种各样的词法分析程序。不过编译原理在讲解词法分析的时候，重点把正则表达式和自动机原理加了进来，然后以一种十分标准的方式来讲解词法分析程序的产生。这样的做法道理很明显，就是要让词法分析从程序上升到理论的地步。

语法分析部分就比较麻烦一点了。现在一般有两种语法分析算法，LL自顶向下算法和LR自底向上算法。LL算法还好说，到了LR算法的时候，困难就来了。很多自学编译原理的都是遇到LR算法的理解成问题后就放弃了自学。其实这些东西都是只要大家理解就可以了，又不是像词法分析那样非得自己写出来才算真正的会。像LR算法的语法分析器，一般都是用工具Yacc来生成，实践中完全没有比较自己来实现。对于LL算法中特殊的递归下降算法，因为其实践十分简单，那么就应该要求每个学生都能自己写。当然，现在也有不少好的LL算法的语法分析器，不过要是换在非C平台，比如Java,Delphi,你不能运用YACC工具了，那么你就只有自己来写语法分析器。

---