利用栈编写递归函数的非递归算法

我感觉这道题目出得有问题：

假设这道题目用递归来实现，当用户输入的x、y满足x=0 && y>=0或者x>0 && y<0时才合法。但是对于后一种情况，由于y是一个负数，输入的数在递归时传递给递归函数时的形式为x-1和2y，2y是永远不会变成一个大于等于0的数的，因此x=0 && y>=0就无法作为递归结束的条件。因此，这个函数有问题。如果函数改为：

g(x,y)=0 x=0,y>=0

g(x,y)=g(x-1,2y)+y x>0,y>0

倒是可以实现。

我以我改过的函数写一个示例，掌握了方法才是王道。

http://hibaiducom/mayadong7349/blog/item/d82c8803e8ee6d161c9583cahtml

如果我的理解有误，你可以HI我，接着探讨。

使用递归的方法，系统会为你这个递归问题分配一个栈空间，这个栈空间的大小是有限制的；然后，系统会把那些暂时不能计算的函数，地址以及参数入栈，直到递归条件成立的时候，才一个个的出栈；所以你那个问题的根本原因是：堆栈空间不够的问题；

你可以看看系统堆栈的大小，比如你在main函数里面这样写：

int x,y;

printf("x:0x%x,y:0x%x\n",&x,&y);

看看这里面的x,y的地址是咋样的，就知道了；在PC里面，栈是倒立放着的，也就是说栈底的地址要大，所以根据这个，就可以估计出系统分配的栈空间大概有多大；然后，你就可以估计递归的深度有多少了。

需要说明的是：不同函数的递归，递归深度是不同的；因为，每个函数占用的栈空间大小不同；

在平时编程的时候，不建议使用递归方法，你可以在堆里面自定义一个栈，然后把递归算法改写成非递归的方法。

你可以在Visual C++ 60 里面建立一个控制台Win32程序，增加异常处理代码，头文件

#include <exceptionh>

try{

return_function();

}catch(runtime_exception){ //这里记得不太清楚，自己搜搜看

//打印出问题

}

个人建议：你要学习c++的话，研究一下《c++ primer》和《深入浅出的MFC》；对于你这些类似的问题，可以搜索：堆分配，栈分配，异常，__thiscall，__stdcall 等关键字，多了解了解

递归就是一个函数在它的函数体内调用它自身。执行递归函数将反复调用其自身，每调用一次就进入新的一层。递归函数必须有结束条件。 

当函数在一直递推，直到遇到墙后返回，这个墙就是结束条件。 

所以递归要有两个要素，结束条件与递推关系。

递归有两个基本要素：

（1）边界条件：确定递归到何时终止，也称为递归出口。

（2）递归模式：大问题是如何分解为小问题的，也称为递归体。递归函数只有具备了这两个要素，才能在有限次计算后得出结果 

在递归函数中，调用函数和被调用函数是同一个函数，需要注意的是递归函数的调用层次，如果把调用递归函数的主函数称为第0层，进入函数后，首次递归调用自身称为第1层调用；从第i层递归调用自身称为第i+1层。反之，退出第i+1层调用应该返回第i层。

一个递归函数的调用过程类似于多个函数的嵌套的调用，只不过调用函数和被调用函数是同一个函数。为了保证递归函数的正确执行，系统需设立一个工作栈。具体地说，递归调用的内部执行过程如下：

（1）运动开始时，首先为递归调用建立一个工作栈，其结构包括值参、局部变量和返回地址；

（2）每次执行递归调用之前，把递归函数的值参和局部变量的当前值以及调用后的返回地址压栈；

（3）每次递归调用结束后，将栈顶元

扩展资料：

递归就是某个函数直接或间接地调用了自身，这种调用方式叫做递归调用。说白了，还是函数调用。既然是函数调用，那么就有一个雷打不动的原则：所有被调用的函数都将创建一个副本，各自为调用者服务，而不受其他函数的影响。

你的ff函数，递归多少次，就有多少个副本，再利用内存的栈式管理，反向退出。这个最好找一下“栈”这方面的东西看看，挺容易的，就像子d匣一样，先进后出。

从某种意义上说，这是不对的，因为就像刚才说的，一旦被调用，他将在内存中复制出一份代码，再被调用就再复制一份，换句话说，你可以吧同一个函数的多次调用理解称谓多个不同函数的一次调用，这样也会会简单些。

再说=1和=0是为什么退出。递归，很需要注意的就是死递归，也就是说，某一个函数进入了无限调用自身的情况，永无止境地消耗内存等资源，这在编程方面是一大忌。

但凡是递归的函数，一定会在某一个地方存在能够返回上一层函数的代码，否则必定死递归。ff函数中，那个else就是返回的出口，你可以这样想，如果没有那个if来进行判断，你递归到什么时候算完？ff是不是会一直调用自己。

因为一旦某个函数A中调用了函数B（或者自己），那么A中的代码会停在调用的位置，而转向B中去执行，同理，如果B又调用函数C，那么B又停在调用的位置，去执行C，如果无限调用，那么程序是永远不会结束的。

当然，也有这种情况，A调用B，然后继续自己的代码，不管B的死活，这种不在我们的讨论范围内，因为那牵扯到另一种编程方式：多线程。

参考资料：

//由于整数的位数是不确定的，可以很长，所以不能用int类型

//为了能表示长整数，我们采用字符串来表示

//一下的代码是用c++写的，和c区别不大

#include<iostream>

#include<cstring>

using namespace std;

void revstr1(char str){

int length=strlen(str);

if(length>0){

char c=(str+length-1);

(str+length-1)='\0';

cout<<revstr1(str);

cout<<c;

}

}

void revstr2(char str){

char p;

int length=strlen(str);

//从后面将整数反序输出

for(p=str+length-1; p>=str,p--)

cout<<p;

//补上换行符

cout<<endl;

}

void main(){

//整数最大长度100，可以调节

char str[101];

cingetline(str,100);

//递归输出

revstr1(str);

//补上换行符

cout<<endl;

//非递归输出

revstr2(str);

return 0;

}

问题一：递归算法还不是很理解!!高手教一教! 递归（recursion）是指把一个大的问题转化为同样形式但小一些的问题加以解决的方法。C语言允许一个函数调用它本身，这就是递归调用。即在调用一个函数的过程中又直接或间接地调用函数本身。不加控制的递归都是无终止的自身调用，程序中是绝对不应该出现这种情况的。为了防止无休止的递归，程序中应控制递归的次数，在某条件成立时进行递归，条件不成立不进行递归调用。并且在递归的调用过程中，不断改变递归的条件，以使递归条件不再成立。

同一问题可能既可以用递归算法解决，也可以用非递归算法解决，递归往往算法设计简单，出奇制胜，而普通算法（通常用循环解决）往往设计稍复杂。但执行效率递归算法逊于循环算法。递归反复调用自己，需要占用较多内存和计算机时间。但有一些问题只有用递归方法才能解决，如著名的汉诺塔问题。

递归程序设计的关键就是考虑问题的两种情况，一种是普遍情况即函数值等于把问题递推一步后的本函数的调用，一种是极端或端点情况，此时函数值有确定的一个值而无须再调用本函数。递归的过程就是从普遍情况逐步过渡到端点情况的过程。

例子：

5个坐在一起论年龄，问第五个人多少岁？他说比第四个人大两岁。问第四个人多少岁，他说比第三个人大两岁。问第三个人多少岁，他说比第二个人大两岁。问第二个人多少岁，他说比第一个人大两岁。问第一个人多少岁，他说10岁。请问第五个人几岁？

int age(int n)

{ int x;

if(n>1) x=age(n-1)+2;

else if(n==1) x=10;

return x;

}

void main( )

{ printf(%d,age(5));}

问题二：什么是递归算法 递归算法就是一个函数通过不断对自己的调用而求得最终结果的一种思维巧妙但是开销很大的算法。

比如：

汉诺塔的递归算法：

void move(char x,char y){

printf(%c-->%c\n,x,y);

}

void hanoi(int n,char one,char two,char three){

/将n个盘从one座借助two座，移到three座/

if(n==1) move(one,three);

else{

hanoi(n-1,one,three,two);

move(one,three);

hanoi(n-1,two,one,three);

}

}

main(){

int n;

printf(input the number of diskes:);

scanf(%d,&n);

printf(The step to moving %3d diskes:\n,n);

hanoi(n,'A','B','C');

}

我说下递归的理解方法

首先：对于递归这一类函数，你不要纠结于他是干什么的，只要知道他的一个模糊功能是什么就行，等于把他想象成一个能实现某项功能的黑盒子，而不去管它的内部 *** 作先，好，我们来看下汉诺塔是怎么样解决的

首先按我上面说的把递归函数想象成某个功能的黑盒子，void hanoi(int n,char one,char two,char three); 这个递归函数的功能是：能将n个由小到大放置的小长方形从one 位置，经过two位置 移动到three位置。那么你的主程序要解决的问题是要将m个的汉诺块由A借助B移动到C，根据我们上面说的汉诺塔的功能，我相信傻子也知道在主函数中写道：hanoi(m,A,B,C)就能实现将m个块由A借助B码放到C，对吧？所以，mian函数里面有hanoi(m,'A','C','B');这个调用。

接下来我们看看要实现hannoi的这个功能，hannoi函数应该干些什么？

在hannoi函数里有这么三行

hanoi(n-1,one,three,two);

move(one,three);

hanoi(n-1,two,one,three);

同样以黑盒子的思想看待他，要想把n个块由A经过B搬到C去，是不是可以分为上面三步呢？

这三部是：第一步将除了最后最长的那一块以外的n-1块由one位置经由three搬到two 也就是从A由C搬到B 然后把最下面最长那一块用move函数把他从A直接搬到C 完事后 第三步再次将刚刚的n-1块借助hanno处函数的功能从B由A搬回到C 这样的三步实习了n块由A经过B到C这样一个功能，同样你不用纠结于hanoi函数到底如何实现这个功能的，只要知道他有这么一个神奇的功能就行

最后：递归都有收尾的时候对吧，收尾就是当只有一块的时候汉诺塔怎么个玩法呢？很简单吧，直接把那一块有Amove到C我们就完成了，所以hanoni这个函数最后还要加上 if(n==1)move(one,three);（当只有一块时，直接有Amove到C位置就行）这么一个条件就能实现hanoin函数n>=1时>>

问题三：怎么更好地终极理解递归算法 递归的基本思想是把规模大的问题转化为规模小的相似的子问题来解决。在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一个方法，所以就产生了函数调用它自身的情况。另外这个解决问题的函数必须有明显的结束条件，这样就不会产生无限递归的情况了。

需注意的是，规模大转化为规模小是核心思想，但递归并非是只做这步转化，而是把规模大的问题分解为规模小的子问题和可以在子问题解决的基础上剩余的可以自行解决的部分。而后者就是归的精髓所在，是在实际解决问题的过程。

问题四：怎样才能深刻理解递归和回溯？ 递归的精华就在于大问题的分解，要学会宏观的去看问题，如果这个大问题可分解为若干个性质相同的规模更小的问题，那么我们只要不断地去做分解，当这些小问题分解到我们能够轻易解决的时候，大问题也就能迎刃而解了。如果你能独立写完递归创建二叉树，前序、中序、后序递归遍历以及递归计算二叉树的最大深度，递归就基本能掌握了。

回溯本人用得很少，仅限于八皇后问题，所以帮不上啥了。

问题五：二叉树的递归算法到底该怎么理解 这不就是在二叉排序树上的递归查找，看程序

tree& find(const T& d, tree& t){

if(t==NULL) return t;如果二叉树为空则返回空，查找失败

if(t->data==d) return t;否则，如果当前根结点关键码为d，则查找成功，当前根结点为待查找结点

if(d>t->data) return find(d, t->right);如果比根的关键码大就递归查找右子树

return find(d, t->left);如果比根的关键码小就递归查找左子树

}

二叉树的递归定义的含义就是非空二叉树，除了根以外，左右子树都是二叉树（可以为空）

问题六：怎么理解递归算法我看了代码但还是不理解 函数自己调用自己就是递归啊。

从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事。讲的内容是：

从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事，讲

从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事……

跟循环差不多。而且浪费栈空间，效率不高。能够转化为循环最好。

问题七：数据结构中的二叉树中的递归怎么理解？ 以中序遍历为例，思想是：

若二叉树为空，则空 *** 作；否则

（1）中序遍历左子树

（中序遍历左子树时也是这三步）

（2）访问根结点

（3）中序遍历右子树

（当然右子树也是重复着三步）

示例代码：

int InOrderTraverse(BiTree T)

{

if(T)

{

InOrderTraverse(T->lchild);

printf(%d\t,T->data);

InOrderTraverse(T->rchild);

}

return OK;

}

问题八：java递归算法，怎么理解？？？ n! = (n-1)n！

简单理解，就是目前的所有任务，等于前面所有的任务+现在的任务。

比如你求 1。。。100的加法总和

实际上是 1 99 的加法总和 + 100 就是了。

这就是递归的来源。

你只需要计算你前一步的任务，然后加上自己，就OK了。

前一步，在再次调用前前一步

问题九：新手一个，有什么更好理解递归的方法吗？（c++） 递归的话就是重复调用方法直到满足条件为止就停止这个方法，就跟循环类似，不过循环使用的方法一边比较简单

问题十：递归的原理解释 递归的底层实现其实是一个栈栈的特点是后进先出,也就是最后进入栈的事件是最先被处理的

递归就是这样运作比如计算阶乘函数F(n)=n!=nF(n-1)=

写成递归,我用java

public static long F(long num){

if(num

#include<stdioh>

#include <stdlibh>

#include <mathh>

#include <timeh>

#include<conioh>

int randbit(int t,int l);

double fn(int k,int j,int m,int n,int b[10][20],int p);

struct gen

{

int chrom[50];

int x[50][20];

};

struct gen gen_group[20];

struct gen gen_x[20];

void main()

{

int i,j,k,p,SUM=20;

int n,m,SUMCAR=0;double M=0;

int b[10][20];double a[20];double g[50][20];int d[10];

printf("请输入需要装配的车型数:");

scanf("%d",&n);

printf("请输入装配线上需要的零部件种类总数:");

scanf("%d",&m);

for(i=1;i<=n;i++)

{

for(j=1;j<=m;j++)

{

printf("请输入生产每辆第%d种车型需要的零部件%d的数量：",i,j);

scanf("%d",&b[i][j]);

}

}

for(i=1;i<=n; i++)

{

for(j=1;j<=m;j++)

printf("%4d",b[i][j]);

printf("\n");

}

for(i=1;i<=n; i++)

{

printf("请输入装配%d车型的数量:",i);

scanf("%d",&d[i]);

SUMCAR+=d[i];

}

printf("总车辆数SUMCAR=%d\n",SUMCAR);

for(j=1;j<=m;j++)

{

for(i=1;i<=n; i++)

M+=d[i]b[i][j];

a[j]=M/SUMCAR;

printf("参数a[%d]的值为：%f\n",j,a[j]);

}

for( i = 0 ; i<SUM; i++ )

for(k=0;k<50;k++)

gen_group[i]chrom[k]= 0;

for( i = 0 ; i<SUM; i++ ) /SUM 20 总共的染色体数量 /

{

for(k=1;k<=11;k++)

gen_group[i]chrom[k]= randbit(1,4); /struct gen gen_group[SUM] 定义一个含有20个染色体的组 /

/ printf("%5d",gen_group[i]chrom[k]);

}

printf("\n");/

}

for(j=0;j<20;j++)

for(k=0;k<50;k++)

for(i=0;i<20;i++)

gen_x[j]x[k][i]=0;

/

for( i = 0 ; i<SUM; i++ )

{

for(k=1;k<=11;k++)

printf("%d",gen_group[i]chrom[k]); /struct gen gen_group[SUM] 定义一个含有20个染色体的组 /

/ printf("%5d",gen_group[i]chrom[k]);

}

printf("\n");

}

/

for(i=0;i<SUM;i++)

{

for(k=1;k<=SUMCAR;k++)

{

for(j=1;j<=4;j++)

{

//printf("%d+",gen_group[i]chrom[k]);

if(gen_group[i]chrom[k]==j)

gen_x[i]x[k][j]=1;

else gen_x[i]x[k][j]=0;

}

}

} printf("\n");

/for(i=0;i<SUM;i++){

for(k=1;k<=SUMCAR;k++)

{

for(j=1;j<=4;j++)

{

printf("%d", gen_x[i]x[k][j]);

}

printf("\n");

}

}/

for(k=0;k<=50;k++) /对g[k][j]赋初值for(k=0;k<=50;k++)/

for(j=0;j<=20;j++)

g[k][j]=0;

for(p=0;p<SUM;p++)

{

for(k=1;k<=SUMCAR;k++)/计算g[k][j]的值/

for(j=1;j<=m;j++)

g[k][j]=fn(k,j,m,n,b,p);

printf("%15f",g[k][j]);

}

getch();

}

int randbit(int t, int l)/ 产生在i与j之间的一个随机数 /

{

int a , b;

b = l - t + 1;

a = t + rand() b / 32768;

return a;

}

double fn(int k,int j,int m,int n,int b[10][20],int p)

{

double h;int i;

if(k>0)

{

printf("+%d+",h);

for(i=1;i<=n;i++)

h=fn(--k,j,m,n,b,p)+gen_x[p]x[k][i]b[i][j]; //你以k为标准,k的值要变化才行

}

//std::system("pause");

return h;

}

你以k为标准,k的值要变化才行 这里就没有管你的结果了,公式上的错误,自己搞定吧

#include "stdioh"

void main()

{

int i=5;

void palin(int n); //声明放在这里

printf("\40:");

palin(i);

printf("\n");

}

void palin( int n ) //这里的应该是函数的实现。

{

char next;

if(n<=1)

{

next=getchar();

printf("\n\0:");

putchar(next);

}

else

{

next=getchar();

palin(n-1);

putchar(next);

}

}