递归算法和栈有什么关系?栈又是怎样运用的?

递归算法和栈都有后进先出这个性质，基本上能用递归完成的算法都可以用栈完成，都是运用后进先出这个性质的
用栈之前首先你要想明白你需要使用“后进先出”干什么，然后才可编写算法，使用中往往是先把数据都压入栈中，然后使用使取出便可，
像表达式求解就是典型的运用栈的例子，可以去看看，会对栈的理解印象深刻些
# include
# define origial 100
# define add 10
typedef struct
{
int *base;
int *top;
int stack;
}opno;
typedef struct
{
char *base;
char *top;
int stack;
}optr;
void initstacka(opno *a)
{
a->base=(int *)malloc(sizeof(int)*origial);
a->top=a->base;
a->stack=origial;
}
void initstackb(optr *b)
{
b->base=(char *)malloc(sizeof(char)*origial);
b->top=b->base;
b->stack=origial;
*b->top++='#';
}
void pusha(opno *a,int b)
{
if(a->top-a->base>=a->stack)
{
a->base=(int *)realloc(a->base,sizeof(int)*(a->stack+add));
a->top=a->base+a->stack;
a->stack+=add;
}
*a->top++=b;
}
void pushb(optr *b,char c)
{
if(b->top-b->base>=b->stack)
{
b->base=(char *)realloc(b->base,sizeof(char)*(b->stack+add));
b->top=b->base+b->stack;
b->stack+=add;
}
*b->top++=c;
}
int determine(char c)
{
if(c>='0'&&c<='9')
return(1);
else
return(0);
}
char gettopb(optr *b)
{
char a;
a=*(b->top-1);
return(a);
}
char shuzu(int i,int j)
{
char a[7][7]={{'>','>','<','<','<','>','>'},{'>','>','<','<','<','>','>'},{'>','>','>','>','<','>','>'},{'>','>','>','>','<','>','>'},{'<','<','<','<','<','=','0'},{'>','>','>','>','0','>','>'},{'<','<','<','<','<','0','='}};
return(a[i][j]);
}
char precede(char b,char a)
{
int i,j;
char s;
switch(b)
{
case '+':i=0;
break;
case '-':i=1;
break;
case '*':i=2;
break;
case '/':i=3;
break;
case '(':i=4;
break;
case ')':i=5;
break;
case '#':i=6;
break;
}
switch(a)
{
case '+':j=0;
break;
case '-':j=1;
break;
case '*':j=2;
break;
case '/':j=3;
break;
case '(':j=4;
break;
case ')':j=5;
break;
case '#':j=6;
break;
}
s=shuzu(i,j);
return(s);
}
void popb(optr *a,char *b)
{
*b=*--a->top;
}
void popa(opno *a,int *b)
{
*b=*--a->top;
}
int count(int a,int b,char c)
{
int sum=0;
switch(c)
{
case '+':sum=a+b;
break;
case '-':sum=a-b;
break;
case '*':sum=a*b;
break;
case '/':sum=a/b;
break;
}
return(sum);
}
int empty(optr *a)
{
if(a->top==a->base)
return(1);
else
return(0);
}
void main()
{
opno *a;
optr *b;
char c;
char d[50];
int i=0,j=0,k,sum=0,p,o,r,w;
int y[3];
a=(opno *)malloc(sizeof(opno));
b=(optr *)malloc(sizeof(optr));
initstacka(a);
initstackb(b);
printf("请输入表达式！\n");
scanf("%s",d);
while(d[i]!='#'&&d[i]!='\0')
if(determine(d[i]))
{
sum=0;
y[j]=d[i]-'0';
while(determine(d[i+1]))
{
i=i+1;
y[++j]=d[i]-'0';
}
for(k=0;k<=j;k++)
sum=sum*10+y[k];
if(sum!=0)
pusha(a,sum);
else
pusha(a,y[0]);
j=0;
for(k=0;k<3;k++)
y[k]=0;
i=i+1;
}
else
{
switch(precede(gettopb(b),d[i]))
{
case '>':popb(b,&c);
popa(a,&p);
popa(a,&o);
r=count(o,p,c);
pusha(a,r);
break;
case '=':popb(b,&c);
i++;
break;
case '<':pushb(b,d[i]);
i++;
break;
}
}
popb(b,&c);
while(c!='#')
{
popa(a,&o);
popa(a,&p);
r=count(o,p,c);
pusha(a,r);
popb(b,&c);
}
popa(a,&w);
printf("%d",w);
}
这就是运用栈写得表达式求值

算法是算法，栈是一种存储方式，一般调用递归算法，层数太多的话会占用很多堆栈空间，可能导致存储空间不够应该注意一下
别的很多算法都可以利用堆栈的思想保存一些数据做后续处理了
int func(int m){
if(m==1)return 1;
return m+func(m-1);
}
这样的话调用func(1000)会将1000,999.....1入栈，然后逐个往上退回

个人的理解，栈 是 先进后出。。递归的话是程序运行到某个点的时候，调用自身，这个时候，之前没运行完的程序会暂时不运行，等到下一层调用完了之后再运行。。这个正是符合栈的先进后出。。这个时候就会有个进栈。。。等到下一层调用完运行了。。之后就可以出栈继续运行。
至于 栈是怎样运用的 个人认为，这种数据结构主要是了解他的一些特点，和算法相辅相成。。没有必要去说某一种算法对应于某一种数据结构。。。在了解了特点之后灵活应用就是了

递归是一种程序设计的方式和思想。计算机在执行递归程序时，是通过栈的调用来实现的。
栈，从抽象层面上看，是一种线性的数据结构，这中结构的特点是“先进后出”，即假设有a，
b，c三个元素，依次放某个栈式存储空间中，要从该空间中拿到这些元素，那么只能以c、b、a的顺序得到。
递归程序是将复杂问题分解为一系列简单的问题，从要解的问题起，逐步分解，并将每步分解得到的问题放入“栈”中，这样栈顶是最后分解得到的最简单的问题，
解决了这个问题后，次简单的问题可以得到答案，以此类推。
分解问题是进栈（或者说压栈）的过程，解决问题是一个出栈的过程。