2024年9月简述递归算法的步骤（三次递归怎么做）

　　⑴简述递归算法的步骤（三次递归怎么做

　　⑵递归算法是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数（或过程来表示问题的解。一个过程(或函数)直接或间接调用自己本身，这种过程（或函数叫递归过程（或函数。递归过程一般通过函数或子过程来实现。递归方法：在函数或子过程的内部，直接或者间接地调用自己的算法。特点递归算法是一种直接或者间接地调用自身算法的过程。在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。递归算法解决问题的特点：()递归就是在过程或函数里调用自身。()在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。()递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。()在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。要求递归算法所体现的“重复”一般有三个要求：一是每次调用在规模上都有所缩小(通常是减半)；二是相邻两次重复之间有紧密的联系，前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)；三是在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件)，无条件递归调用将会成为死循环而不能正常结束。

　　⑶递归做为一种算法在程序设计语言中广泛应用.是指函数/过程/子程序在运行过程序中直接或间接调用自身而产生的重入现像.程序调用自身的编程技巧称为递归（recursion。一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。注意：()递归就是在过程或函数里调用自身;()在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口，否则将无限进行下去（死锁。递归算法一般用于解决三类问题：()数据的定义是按递归定义的。(Fibonai函数)()问题解法按递归算法实现。(回溯)()数据的结构形式是按递归定义的。(树的遍历，图的搜索)递归的缺点：递归算法解题的运行效率较低。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。

　　⑷举个简单的例子吧,****;#include《iostream》usingnamespacestd;intFun(intval){if(n》)returnval*Fun(val-);//最难理解的相信就是这一步吧returnval;}intmain(){cout《《Fun()《《endl;return;}首先,第一次调用Fun函数时,val==;所以好好分析一下这段代码if(val》)returnval*Fun(val-);第一次调用时val==,条件成立,函数返回val(等于那个)乘以用实参(也就是val-的值)调用的那个函数的返回值(也就是自身)...看到这里先不要头晕,这只是第一步,还有很多步调用,其实跟循环是差不多的.函数调用有一个返回值,如果返回值是一个表达式,就先求解表达式的值再返回,被函数返回时从调用函数处的下一个语句继续执行,如果没有理解C语言的这两句话,这就很难理解递归了.下面是整个程序的流程,用val==调用Fun,执行到if语句,条件成立执行returnval*Fun(val-),由于函数调用操作符()优先级高于算术操作符,因此表达式的求解顺序是先调用函数,再用val*返回值;,用val==的值调用Fun,后面的步骤和用val==调用Fun的步骤是一样的;,用val==的值调用Fun;,用val==的值调用Fun;,用val==的值调用Fun,这时的if语句条件不成立,于是执行后面的returnval的值(==);,那这个val==的值返回到哪里去了呢?刚接触递归的人可能会很容易联想到是main函数调用Fun的,那这个值也返回到main函数中去了.其实不是,返回值为的Fun函数是谁调用的?是val==时的Fun函数调用的,也就是第步的if语句后面的表达式是return*Fun(-),理解这点就好办了,第六步就开始求解前面还没执行的算术操作(由于函数调用操作符()优先级高于算术操作符,因此表达式的求解顺序是先调用函数).也就是把第步的返回值用于求解第步时里的表达式;,在上一步骤中,求解出*Fun(val-)的值,又把它返回给它的调用者,就是把值返回至第步;,把第步的得出的值返回第步;,把第步得出的值返回第步;,在第步,记得这次调用是main函数调用的,因此返回到main函数中的cout《《Fun()《《endl,输出结果;整个递归过程就完成了,可以看到递归也是一个循环,但它比一般的循环计算的步骤多了很多,所以它的效率普遍是比较低的,而且操作系统把每一次的调用装进一个栈中记录起来,它耗费的内存也是比较大的,在深层的递归调用或在递归函数中定义较大的数据容易造成栈溢出,但有时(对初学者来说不见得)用它来解决问题却能让代码清晰,容易编写.

　　⑸递归算法（英语：recursionalgorithm在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。

　　⑹递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。

　　⑺计算理论可以证明递归的作用可以完全取代循环，因此在很多函数编程语言（如Scheme中习惯用递归来实现循环。

　　⑻在支持自调用的编程语言中，递归可以通过简单的函数调用来完成，如计算阶乘的程序在数学上可以定义为：

　　⑼这一程序在Scheme语言中可以写作：

　　⑽(define?(factorial?n)??(if?(=?n?)????????????(*?n?(factorial?(-?n?)))))

　　⑾即使一个编程语言不支持自调用，如果在这语言中函数是第一类对象（即可以在运行期创建并作为变量处理，递归可以通过不动点组合子（英语：Fixed-pointbinator来产生。以下Scheme程序没有用到自调用，但是利用了一个叫做Z算子（英语：Zbinator的不动点组合子，因此同样能达到递归的目的。

　　⑿(define?Z??(lambda?(f)????((lambda?(recur)?(f?(lambda?arg?(apply?(recur?recur)?arg))))?????(lambda?(recur)?(f?(lambda?arg?(apply?(recur?recur)?arg)))))))(define?fact??(Z?(lambda?(f)???????(lambda?(n)?????????(if?(《=?n?)??????????????????????????(*?n?(f?(-?n?))))))))

　　⒀这一程序思路是，既然在这里函数不能调用其自身，我们可以用Z组合子应用(application)这个函数后得到的函数再应用需计算的参数。

　　⒁尾部递归是指递归函数在调用自身后直接传回其值，而不对其再加运算。尾部递归与循环是等价的，而且在一些语言（如Scheme中可以被优化为循环指令。因此，在这些语言中尾部递归不会占用调用堆栈空间。以下Scheme程序同样计算一个数字的阶乘，但是使用尾部递归：

　　⒂(define?(factorial?n)??(define?(iter?product?counter)????(if?(》?counter?n)????????product????????(iter?(*?counter?product)??????????????(+?counter?))))??(iter??))

　　⒃百科-递归算法.百度百科

　　⒄java中递归算法是什么怎么算的

　　⒅Java递归算法是基于Java语言实现的递归算法。递归算法是一种直接或者间接调用自身函数或者方法的算法。递归算法实质是把问题分解成规模缩小的同类问题的子问题，然后递归调用方法表示问题的解。递归往往能给我们带来非常简洁非常直观的代码形式，从而使我们的编码大大简化，然而递归的思维确实跟我们的常规思维相逆的，通常都是从上而下的思维问题，而递归趋势从下往上的进行思维。

　　⒆递归算法解决问题的特点：

　　⒇递归就是方法里调用自身。

　　⒈在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。

　　⒉递归算法代码显得很简洁，但递归算法解题的运行效率较低。所以不提倡用递归设计程序。

　　⒊在递归调用的过程中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等，所以一般不提倡用递归算法设计程序。

　　⒋在做递归算法的时候，一定把握出口，也就是做递归算法必须要有一个明确的递归结束条件。这一点是非常重要的。其实这个出口就是一个条件，当满足了这个条件的时候我们就不再递归了。

　　⒌public?class?Factorial?{????//this?is?a?recursive?function????int?fact(int?n){????????if?(n==)?return?;????????return?fact(n-)*n;????}?????}

　　⒍public?class?TestFactorial?{?????public?static?void?main(String?args)?{????????//?TODO?Auto-generated?method?stub????????Factorial?factorial=new?Factorial();????????System.out.println(“factorial()=“+factorial.fact());????}}

　　⒎代码执行流程图如下：

　　⒏此程序中n=就是程序的出口。

　　⒐一个递归算法必须包括什么

　　⒑递归算法包含的两个部分：

　　⒒由其自身定义的与原始问题类似的更小规模的子问题（只有数据规模不同，它使递归过程持续进行，称为一般条件。

　　⒓所描述问题的最简单的情况，它是一个能控制递归过程结束的条件，称为基本条件。（递归出口

　　⒔如果一个对象部分地由它自身组成或按它自己定义，则称它是递归的，所以说递归就是函数/过程/子过程在运行过程中直接或间接调用自身而产生的重入现象。

　　⒕就是把一个规模大的问题分为若干个规模较小的子问题求解，而每一个子问题又可以分为几个规模更小的子问题。基本上，所有的递归问题都可以用递推公式来表示。

　　⒖最重要的一点就是假设子问题已经解决了，现在要基于已经解决的子问题来解决当前问题；或者说，必须先解决子问题，再基于子问题来解决当前问题或者可以这么理解：递归解决的是有依赖顺序关系的多个问题。

　　⒗优点：逻辑清楚，结构清晰，可读性好，代码简洁，效率高（拓展：DFS深度优先搜素，前中后序二叉树遍历

　　⒘缺点：函数调用开销大，空间复杂度高，有堆栈溢出的风险

　　⒙个函数调用其自身，就是递归.递归和普通函数调用一样是通过栈实现的.树与二叉树适合使用递归的形式来表述.算法分为基础步和归纳步递归算法是将归纳法的思想应用于算法设计之中，递归算法充分地利用了计算机系统内部机能，自动实现调用过程中对于相关且必要地信息的保存与回复（问题的描述涉及规模（问题的规模发生变化后，解决问题的方法完全相同，并且原问题的解由小规模问题的解构成（小规模的问题是可以求解的（在有限步内可以停机输入：n输出：n！输入：盘子的个数n、柱子的名称a,b,c输出：移动方案输入：位数n输出：斐波那契数列第n位的值有n阶楼梯，每次只能下一个或者两个，计算一共有多少种下楼方法算法思想：.将n个数均分为s和s.分别求解s和s的最大值和最小值s最大值为max，s最小值为mins最大值为max，s最小值为min.计算min(min,min),max(max,max)

　　⒚谁能解释一下用递归做的排列算法的详细步骤参考王晓东的《计算机算法设计与分析》p

　　⒛用到递归的排序算法有快速排序和归并排序。快速排序：先选最开始的元素为枢轴，然后分别从两头中的一头开始与枢轴比较。后面的应该大于枢轴，前面的应该小于枢轴，不然则交换（前面与后面，最后确定下来的位置（前后重合就是枢轴的位置。这样一来原序列就一分为二。不断递归，再一分为二，最后直到被分为的两端中有一个元素单独的时候就结束分割。归并排序:第一次两个两个的来，排序之后就归并成一个有序列，然后再四个四个的来，排序之后归并成一个有序列……直到最后两个归并为一个有序列。

　　递归算法是怎么运行的

　　递归算法是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数（或过程来表示问题的解。一个过程(或函数)直接或间接调用自己本身，这种过程(或函数)叫递归过程(或函数)。递归算法递归算法流程递归过程一般通过函数或子过程来实现。递归方法：在函数或子过程的内部，直接或者间接地调用自己的算法。算法简析递归是计算机科学的一个重要概念，递归的方法是程序设计中有效的方，采用递归编写递归能使程序变得简洁和清晰。