return; 返回调用点;
创新互联建站是专业的江川网站建设公司,江川接单;提供成都网站设计、做网站,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行江川网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!
非递归,返回调用他的那个函数,调用他的那个地方;
递归调用,返回自己调用自己的地方,或者第一次调用他的地方,这个只有分析代码才知道具体情况。
无返回值函数,相当于,BASIC 的子程序,pascal 的过程,返回调用语句处,以便执行下一条语句,实际返回点是下一条指令,然后可能还要,再执行些,调用后的扫尾的工作,才来到下一步执行。
有返回值函数,返回使用函数值的地方。
不管哪一种,都是返回调用处,继续向下执行。
函数调用,首先要执行计算参数的任务,然后执行参数传递的工作,然后才轮到调用函数。
函数调用前,可能还要保存现场,具体就是寄存器压栈保存,防止函数调用时,现场被破坏
调用完成,要恢复现场,恢复寄存器的值,具体就是从堆栈中,弹出保存的寄存器数据值。
递归函数,一般包含:
1)退出条件,适当条件下函数退出递归。
2)递归部分(自调用,并适当更新,执行条件,函数参数,全局变量等)
3)执行部分,如打印节点信息等。
看递归代码,
1)首先,看何时退出递归(程序不再执行自调用)
2)看递归执行顺序
3)看执行代码,干了什么。和递归部分的执行的先后顺序。
4)有些递归函数,没有独立的执行部分,只有一些表达式,看他先后执行那些表达式。
5)有些递归函数,只看函数本身看不出是递归函数,因为这个函数,会调用别的函数,别的函数又会再回头调用该函数本身。
这就要查看,函数调用链,里面是否调用了自己。
PS:
不管是否递归,函数总是要干点什么的(函数的功能)。
所以,看递归函数,不能光看函数,自己调用自己的,递归部分;
还要看,非递归部分干了什么,这个部分,才是递归实际干的事情;
递归不过是一种重复而已,通过递归部分反复调用自己;
从而重复执行非递归部分,完成递归函数的功能。
C,C++ :return 语句有两个功能
1)返回调用处,程序执行下一步。
2)返回执行的结果
1)这个功能,返回的函数调用的位置,执行下步的程序。
在表达式中,函数调用会得到一个结果,程序解析表达式的时候遇到函数,会调用函数
代码执行,会因此跳到函数内部,开始执行函数内部的程序,执行完毕;
会得到一个结果,这个结果就是函数的返回值,也叫函数值,
这时函数调用就结束了,程序返回继续解析表达式,并用函数返回值代替函数,继续解析(计 算)表达式。
1) 如果表达式比较复杂的话;如果表达式解析没有完成,函数返回解析表达式的断点处,
如果完成了,执行下一条语句,
2)如果表达式比较简单,函数返回后,会执行下一条语句。
单独的一条函数调用,称为函数调用表达式。
所以,C 几乎一切都是表达式。
任何表达式,加上分号,就是一条语句。
所以 单独的函数调用加上分号,构成一条单独的函数调用表达式语句,就是函数调用语句。
函数调用语句,执行完成后返回调用点,执行逻辑上的下一条语句。
总结:
函数返回
1)返回值:函数返回值,放在特定的寄存器中(
X86,WINDOWS WIN32 VC eax---char,int 指针; edx:eax---long long,__int64;协处理器的浮点堆栈寄存器 float,double,long double :ST(0) ),如果返回值的类型,比较长,会使用一个全局变量(static???)存放返回值,并把该全局变量的指针,放在特定的寄存器中(X86,WINDOWS WIN32 VC:
eax)。
2)返回位置:函数结束,程序返回调用点。继续执行。
注意:由于函数可以用在表达式中,所以函数实际返回,解析表达式的断点处,继续解析表达式。
函数调用本身,就是一个表达式,称为函数调用表达式。
程序调用自身的编程技巧称为递归( recursion)。
一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说,递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。
注意:
(1) 递归就是在过程或函数里调用自身;
(2) 在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口
你的递归程序是错的,我转来个对的,带讲解的,你看看。
语言函数的递归和调用
一、基本内容:
C语言中的函数可以递归调用,即:可以直接(简单递归)或间接(间接递归)地自己调自己。
要点:
1、C语言函数可以递归调用。
2、可以通过直接或间接两种方式调用。目前只讨论直接递归调用。
二、递归条件
采用递归方法来解决问题,必须符合以下三个条件:
1、可以把要解决的问题转化为一个新问题,而这个新的问题的解决方法仍与原来的解决方法相同,只是所处理的对象有规律地递增或递减。
说明:解决问题的方法相同,调用函数的参数每次不同(有规律的递增或递减),如果没有规律也就不能适用递归调用。
2、可以应用这个转化过程使问题得到解决。
说明:使用其他的办法比较麻烦或很难解决,而使用递归的方法可以很好地解决问题。
3、必定要有一个明确的结束递归的条件。
说明:一定要能够在适当的地方结束递归调用。不然可能导致系统崩溃。
三、递归实例
例:使用递归的方法求n!
当n1时,求n!的问题可以转化为n*(n-1)!的新问题。
比如n=5:
第一部分:5*4*3*2*1
n*(n-1)!
第二部分:4*3*2*1
(n-1)*(n-2)!
第三部分:3*2*1
(n-2)(n-3)!
第四部分:2*1
(n-3)(n-4)!
第五部分:1
(n-5)!
5-5=0,得到值1,结束递归。
源程序:
fac(int
n)
{int
t;
if(n==1)||(n==0)
return
1;
else
{
t=n*fac(n-1);
return
t;
}
}
main(
)
{int
m,y;
printf(“Enter
m:”);
scanf(“%d”,m);
if(m0)
printf(“Input
data
Error!\n”);
else
{y=fac(m);
printf(“\n%d!
=%d
\n”,m,y);
}
}
四、递归说明
1、当函数自己调用自己时,系统将自动把函数中当前的变量和形参暂时保留起来,在新一轮的调用过程中,系统为新调用的函数所用到的变量和形参开辟另外的存储单元(内存空间)。每次调用函数所使用的变量在不同的内存空间。
2、递归调用的层次越多,同名变量的占用的存储单元也就越多。一定要记住,每次函数的调用,系统都会为该函数的变量开辟新的内存空间。
3、当本次调用的函数运行结束时,系统将释放本次调用时所占用的内存空间。程序的流程返回到上一层的调用点,同时取得当初进入该层时,函数中的变量和形参所占用的内存空间的数据。
4、所有递归问题都可以用非递归的方法来解决,但对于一些比较复杂的递归问题用非递归的方法往往使程序变得十分复杂难以读懂,而函数的递归调用在解决这类问题时能使程序简洁明了有较好的可读性;但由于递归调用过程中,系统要为每一层调用中的变量开辟内存空间、要记住每一层调用后的返回点、要增加许多额外的开销,因此函数的递归调用通常会降低程序的运行效率。
五、程序流程
fac(int
n)
/*每次调用使用不同的参数*/
{
int
t;
/*每次调用都会为变量t开辟不同的内存空间*/
if(n==1)||(n==0)
/*当满足这些条件返回1
*/
return
1;
else
{
t=n*fac(n-1);
/*每次程序运行到此处就会用n-1作为参数再调用一次本函数,此处是调用点*/
return
t;
/*只有在上一句调用的所有过程全部结束时才运行到此处。*/
}
}
递归(recursion)就是子程序(或函数)直接调用自己或通过一系列调用语句间接调用自己,是一种描述问题和解决问题的基本方法。
递归通常用来解决结构自相似的问题。所谓结构自相似,是指构成原问题的子问题与原问题在结构上相似,可以用类似的方法解决。具体地,整个问题的解决,可以分为两部分:第一部分是一些特殊情况,有直接的解法;第二部分与原问题相似,但比原问题的规模小。实际上,递归是把一个不能或不好解决的大问题转化为一个或几个小问题,再把这些小问题进一步分解成更小的问题,直至每个小问题都可以直接解决。因此,递归有两个基本要素:
(1)边界条件:确定递归到何时终止,也称为递归出口。
(2)递归模式:大问题是如何分解为小问题的,也称为递归体。递归函数只有具备了这两个要素,才能在有限次计算后得出结果
汉诺塔问题:对汉诺塔问题的求解,可以通过以下3个步骤实现:
(1)将塔上的n-1个碟子借助塔C先移到塔B上;
(2)把塔A上剩下的一个碟子移到塔C上;
(3)将n-1个碟子从塔B借助塔A移到塔C上。
在递归函数中,调用函数和被调用函数是同一个函数,需要注意的是递归函数的调用层次,如果把调用递归函数的主函数称为第0层,进入函数后,首次递归调用自身称为第1层调用;从第i层递归调用自身称为第i+1层。反之,退出第i+1层调用应该返回第i层。采用图示方法描述递归函数的运行轨迹,从中可较直观地了解到各调用层次及其执行情况,具体方法如下:
(1)写出函数当前调用层执行的各语句,并用有向弧表示语句的执行次序;
(2)对函数的每个递归调用,写出对应的函数调用,从调用处画一条有向弧指向被调用函数入口,表示调用路线,从被调用函数末尾处画一条有向弧指向调用语句的下面,表示返回路线;
(3)在返回路线上标出本层调用所得的函数值。n=3时汉诺塔算法的运行轨迹如下图所示,有向弧上的数字表示递归调用和返回的执行顺序
三、递归函数的内部执行过程
一个递归函数的调用过程类似于多个函数的嵌套的调用,只不过调用函数和被调用函数是同一个函数。为了保证递归函数的正确执行,系统需设立一个工作栈。具体地说,递归调用的内部执行过程如下:
(1)运动开始时,首先为递归调用建立一个工作栈,其结构包括值参、局部变量和返回地址;
(2)每次执行递归调用之前,把递归函数的值参和局部变量的当前值以及调用后的返回地址压栈;
(3)每次递归调用结束后,将栈顶元素出栈,使相应的值参和局部变量恢复为调用前的值,然后转向返回地址指定的位置继续执行。
上述汉诺塔算法执行过程中,工作栈的变化如下图所示,其中栈元素的结构为(返回地址,n值,A值,B值,C值),返回地址对应算法中语句的行号,分图的序号对应图中递归调用和返回的序号
我可以帮助你,你先设置我最佳答案后,我百度Hii教你。
编程里面估计最让人摸不着头脑的基本算法就是递归了。很多时候我们看明白一个复杂的递归都有点费时间,尤其对模型所描述的问题概念不清的时候,想要自己设计一个递归那么就更是有难度了。今天我也花费了半个小时来搞明白二叉树的平衡性的递归模型,首先我不明白什么叫做平衡性,所以花费的时候大部分实在试探理解平衡性的含义。在搞明白的时候,我突然想到假如让我来设计,在我知道平衡性的前提下,我是否可以建立如此简洁的递归模型。为此,我遇到的问题是我们到底在什么情况下适用递归模型,并且递归模型如何建立。
数学都不差的我们,第一反应就是递归在数学上的模型是什么。毕竟我们对于问题进行数学建模比起代码建模拿手多了。 (当然如果对于问题很清楚的人也可以直接简历递归模型了,运用数模做中介的是针对对于那些问题还不是很清楚的人)
自己观察递归,我们会发现,递归的数学模型其实就是归纳法,这个在高中的数列里面是最常用的了。回忆一下归纳法。
归纳法适用于想解决一个问题转化为解决他的子问题,而他的子问题又变成子问题的子问题,而且我们发现这些问题其实都是一个模型,也就是说存在相同的逻辑归纳处理项。当然有一个是例外的,也就是递归结束的哪一个处理方法不适用于我们的归纳处理项,当然也不能适用,否则我们就无穷递归了。这里又引出了一个归纳终结点以及直接求解的表达式。如果运用列表来形容归纳法就是:
步进表达式:问题蜕变成子问题的表达式
结束条件:什么时候可以不再是用步进表达式
直接求解表达式:在结束条件下能够直接计算返回值的表达式
逻辑归纳项:适用于一切非适用于结束条件的子问题的处理,当然上面的步进表达式其实就是包含在这里面了。
这样其实就结束了,递归也就出来了。
递归算法的一般形式:
void func( mode)
{
if(endCondition)
{
constExpression //基本项
}
else
{
accumrateExpreesion /归纳项
mode=expression //步进表达式
func(mode) / /调用本身,递归
}
}
最典型的就是N!算法,这个最具有说服力。理解了递归的思想以及使用场景,基本就能自己设计了,当然要想和其他算法结合起来使用,还需要不断实践与总结了。
例如:返回一个二叉树的深度:
int depth(Tree t){
if(!t) return 0;
else {
int a=depth(t.right);
int b=depth(t.left);
return (ab)?(a+1):(b+1);
}
}
判断一个二叉树是否平衡:
int isB(Tree t){
if(!t) return 0;
int left=isB(t.left);
int right=isB(t.right);
if( left =0 right =0 left - right = 1 || left -right =-1)
return (leftright)? (right +1) : (left + 1);
else return -1;
}
上面这两个递归的难易程度就不一样了,第一个关于深度的递归估计只要了解递归思想的都可以短时间设计出来,但第二个估计就要长点时间了。纯递归问题的难易主要纠结于一些条件表达式的构造以及初值的设置(上面的为直接表达式值的设定)。
最后需要补充的是,很多不理解递归的人,总认为递归完全没必要,用循环就可以实现,其实这是一种很肤浅的理解。因为递归之所以在程序中能风靡并不是因为他的循环,大家都知道递归分两步,递和归,那么可以知道递归对于空间性能来说,简直就是造孽,这对于追求时空完美的人来说,简直无法接接受,如果递归仅仅是循环,估计现在我们就看不到递归了。递归之所以现在还存在是因为递归可以产生无限循环体,也就是说有可能产生100层也可能10000层for循环。例如对于一个字符串进行全排列,字符串长度不定,那么如果你用循环来实现,你会发现你根本写不出来,这个时候就要调用递归,而且在递归模型里面还可以使用分支递归,例如for循环与递归嵌套,或者这节枚举几个递归步进表达式,每一个形成一个递归。