经典递归算法（递归算法的经典例子）

本文目录

• 递归算法的经典例子
• J**A程序经常用到“递归”,“递归”的基本思想是
• J**A中的递归方法，求讲一下
• 逐层剥离法,判断算法,观察算法的区别
• 递归是什么要详细解释
• java递归算法
• python递归算法经典实例有哪些
• 08《算法入门教程》递归算法之斐波那契数列
• 求经典的递归算法以及案例（可用C#、PHP、J**A其中一种语言来写）!

递归算法的经典例子

具体如下。
递归阶乘n!=n*(n-1)*(n-2)*...*1(n》0)publicstaticIntegerrecursionMulity(Integern){if(n==1){汉诺塔问题publicstaticvoidhanio(intn，chara，charb，charc){判定一系列字符串中是否有相同的内容publicclassCrf。
递归算法（英语：recursionalgorithm）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。计算理论可以证明递归的。

J**A程序经常用到“递归”,“递归”的基本思想是

递归的核心思想是分解。把一个很复杂的问题使用同一个策略将其分解为较简单的问题，如果这个的问题仍然不能解决则再次分解，直到问题能被直接处理为止。
比如求 1+1/2+1/3+...+1/n的和，如果按照我们正常的思维，就会使用一个循环，把所有的表示式的值加起来，这是最直接的办法。如果使用递归的思维，过程就是这样的，要求1+1/2+1/3+...+1/n的值，可以先求s1=1+1/2+1/3+...+1/(n-1)的值，再用s1加上1/n就是所求的值，而求s1的过程又可以使用上面的分解策略继续分解，最终分解到求1+1/2的值，而这个问题简单到我们可以直接解决，自此问题得到解决。
递归强调的分治的策略，再举个例子，有一种排序算法叫归并排序，其思想是这样的：要对一个无序的数组进行排序，可以将这个数组分解为2个小数组，然后对这两个数组分别排序，再把排好序的两个数组合并。而这一过程中只有“对两个数组分别排序”不是我们能解决的，但是这个问题可以使用上面的策略进行再次的分解，最后这个问题就被分解到对2个元素的数组进行排序，而这个问题简单到我们可以直接处理。
上面提到的分解的策略，或者说算法，抽象出来就是我们的函数，因为在这个过程中我们要不同的使用这个策略来不断的分解问题，所以代码上就体现为这个函数会不断的调用自身。还有一点，并不是所有的递归都是可以实现的，或者说有意义的。如果在分解的过程中，问题最终不能分解到一个可以直接解决的问题，则这个过程是没有意义，也就是无限的循环。
具体的代码都不贴了，有兴趣可以百度看看。

J**A中的递归方法，求讲一下

方法递归和循环语句差不多，打个比喻。方法递归是小明上楼拿东西，一楼，二楼，三楼……楼顶。在楼顶拿到想要的东西以后，你总不能直接跳下来吧。你得一层一层的返回下来。循环就是驴拉磨，你转多少圈都是在原地。变化的只是盘子里的东西有变化。方法递归不会进入死循环，但陷的太深系统会崩溃。
答得不好抱歉

逐层剥离法,判断算法,观察算法的区别

（一）递归（recursion）
　直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。每个递归函数都要有非递归定义的初始值。
关键要素：边界条件、递归方程
　典型案例：斐波那契、汉诺塔
（二）分治法（divide and conquer method）
　将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题相同。递归的解这些子问题，然后将各个子问题的解合并得到原问题的解。
　典型案例：二分法、归并排序、快速排序、汉诺塔
（三）动态规划法（dynamic programing method）
　和分治法类似，都是将待求问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。而动态规划的子问题往往是重叠的，即相互不独立，所以可以用一个表来记录所有子问题的解，以免之后大量重复计算。
　关键要素：最优子结构、重叠子问题、状态转移方程
　典型案例：凑零钱、背包问题
（四）贪心法（greedy method）
　贪心算法并不从整体的最优解考虑，而是做出当前的局部最优的选择。两个要素是最优子结构和贪心选择性质，贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择(即贪心选择)来达到。
关键要素：最优子结构、贪心选择性质
　典型案例：无重叠区间、活动安排问题
（五）回溯法（back track method）
　回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法。
两种典型的解空间树：子集树、排列树
　典型案例：N皇后问题、图的m着色问题
（六）分支限界法（branch and bound method）
　分支限界法按广度优先策略遍历问题的解空间，在遍历过程种，对已经处理的每一个结点根据限界函数估算目标函数的可能值，从中选取使目标函数取得极值（极大或极小）的结点优先进行广度优先搜索，从而不断调整搜索方向，尽快找到问题的解。因为界限函数常常是基于问题的目标函数而确定的，所以，分支限界法适用于求解最优化问题。
　常见两种分支限界法:
（1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。
（2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。
　典型案例：0/1背包问题、单源最短路径问题、最优装载问题。
（七）十大经典排序算法
***隐藏网址***
（八）七大查找算法
***隐藏网址***
二、算法差异
（一）分治法和动态规划法的区别
共同点：都是将问题分解为子问题，求解子问题，记录子问题的解，然后合并子问题的解得到原问题的解。
不同点：动态规划解决的问题一定是最优化问题，并且拥有重叠子问题；分治法解决的问题不一定是最优化问题，分解出的子问题是不重叠的，是相互独立的。
（二）动态规划法和贪心法的区别
共同点：贪心算法和动态规划算法都是解决最优化问题，并要求问题具有最优子结构性质。
不同点：
　动态规划：每一步作一个选择——依赖于子问题的解。
　贪心方法：每一步作一个选择——不依赖于子问题的解。
　动态规划方法的条件：最优子结构性质；重叠子问题性质。
　可用贪心方法的条件：最优子结构性质；贪心选择性质。
　动态规划：自底向上求解（动态规划方法是自底向上计算各个子问题的最优解，即先计算子问题的最优解，然后再利用子问题的最优解构造大问题的最优解，因此需要最优子结构）
　贪心方法： 自顶向下求解。
（三）回溯法和分支限界法的区别
共同点：一种在问题的解空间树上搜索问题解的算法。
不同点：
　求解目标不同，回溯法的目标是找出解空间树满足约束条件的所有解，而分支限界法的求解目标是尽快地找出满足约束条件的一个解；
　搜索方法不同，回溯法采用深度优先方法搜索解空间，而分支限界法一般采用广度优先或以最小消耗优先的方式搜索解空间树；
　对扩展结点的扩展方式不同，回溯法中，如果当前的扩展结点不能够再向纵深方向移动，则当前扩展结点就成为死结点，此时应回溯到最近一个活结点处，并使此活结点成为扩展结点。分支限界法中，每一次活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点；
　存储空间的要求不同，分支限界法的存储空间比回溯法大得多，当内存容量有限时，回溯法成功的可能性更大。

递归是什么要详细解释

递归是一种重要的编程技术。该方法用于让一个函数从其内部调用其自身。一个示例就是计算阶乘。0 的阶乘被特别地定义为 1。 更大数的阶乘是通过计算 1 * 2 * ...来求得的，每次增加 1，直至达到要计算其阶乘的那个数。
下面的段落是用文字定义的计算阶乘的一个函数。
“如果这个数小于零，则拒绝接收。如果不是一个整数，则将其向下舍入为相邻的整数。如果这个数为 0，则其阶乘为 1。如果这个数大于 0，则将其与相邻较小的数的阶乘相乘。”
要计算任何大于 0 的数的阶乘，至少需要计算一个其他数的阶乘。用来实现这个功能的函数就是已经位于其中的函数；该函数在执行当前的这个数之前，必须调用它本身来计算相邻的较小数的阶乘。这就是一个递归示例。
递归和迭代（循环）是密切相关的 — 能用递归处理的算法也都可以采用迭代，反之亦然。确定的算法通常可以用几种方法实现，您只需选择最自然贴切的方法，或者您觉得用起来最轻松的一种即可。
显然，这样有可能会出现问题。可以很容易地创建一个递归函数，但该函数不能得到一个确定的结果，并且不能达到一个终点。这样的递归将导致计算机执行一个“无限”循环。下面就是一个示例：在计算阶乘的文字描述中遗漏了第一条规则（对负数的处理） ，并试图计算任何负数的阶乘。这将导致失败，因为按顺序计算 -24 的阶乘时，首先不得不计算 -25 的阶乘；然而这样又不得不计算 -26 的阶乘；如此继续。很明显，这样永远也不会到达一个终止点。
因此在设计递归函数时应特别仔细。如果怀疑其中存在着无限递归的可能，则可以让该函数记录它调用自身的次数。如果该函数调用自身的次数太多，即使您已决定了它应调用多少次，就自动退出。
下面仍然是阶乘函数，这次是用 JScript 代码编写的。
// 计算阶乘的函数。如果传递了
// 无效的数值（例如小于零），
// 将返回 -1，表明发生了错误。若数值有效，
// 把数值转换为最相近的整数，并
// 返回阶乘。
function factorial(aNumber) {
aNumber = Math.floor(aNumber); // 如果这个数不是一个整数，则向下舍入。
if (aNumber 《 0) { // 如果这个数小于 0，拒绝接收。
return -1;
}
if (aNumber == 0) { // 如果为 0，则其阶乘为 1。
return 1;
}
else return (aNumber * factorial(aNumber - 1)); // 否则，递归直至完成。

java递归算法

1.汉诺塔问题
import javax.swing.JOptionPane;
　　public class Hanoi {
　　private static final String DISK_B = "diskB";
　　private static final String DISK_C = "diskC";
　　private static final String DISK_A = "diskA";
　　static String from=DISK_A;
　　static String to=DISK_C;
　　static String mid=DISK_B;
　　public static void main(String args) {
　　String input=JOptionPane.showInputDialog("please input the number of the disks you want me move.");
　　int num=Integer.parseInt(input);
　　move(num，from，mid，to);
　　}
　　private static void move(int num， String from2， String mid2， String to2) {
　　if(num==1){
　　System.out.println("move disk 1 from "+from2+" to "+to2);
　　}
　　else {
　　move(num-1，from2，to2，mid2);
　　System.out.println("move disk "+num+" from "+from2+" to "+to2);
　　move(num-1，mid2，from2，to2);
　　}
　　}
　　}
2. 这是一个排列的例子，它所做的工作是将输入的一个字符串中的所有元素进行排序并输出，例如：你给出的参数是"abc" 则程序会输出：
　　abc
　　acb
　　bac
　　bca
　　cab
　　cba
　　(1)算法的出口在于：low=high也就是现在给出的排列元素只有一个时。
　　(2)算法的逼近过程：先确定排列的第一位元素，也就是循环中i所代表的元素，
　　然后low+1开始减少排列元素，如此下去，直到low=high
　　public static void permute(String str) {
　　char strArray = str.toCharArray();
　　permute(strArray， 0， strArray.length - 1);
　　}
　　public static void permute(char list， int low， int high) {
　　int i;
　　if (low == high) {
　　String cout = "";
　　for (i = 0; i 《= high; i++)
　　cout += list;
　　System.out.println(cout);
　　} else {
　　for (i = low; i 《= high; i++) {
　　char temp = list;
　　list;
　　list = temp;
　　permute(list， low + 1， high);
　　temp = list;
　　list;
　　list = temp;
　　}
　　}
　　}
　　3。这是一个组合的例子，与上述的例子相似，只是它所做的工作是，输出所给字符串中制定数目的元素的组合种类
　　(1)程序出口在于n=1，此时只要输出目标数组的所有元素即可
　　(2)逼近过程，当n》1　的时候，我们先取第一个元素放入目标数组中，然后n-1，如此下去，最后出来。
　　import javax.swing.JOptionPane;
　　public class Combination {
　　/**
　　* @param args
　　*/
　　public static void main(String args) {
　　String input = JOptionPane.showInputDialog("please input your String： ");
　　String numString = JOptionPane.showInputDialog("please input the number of your Combination： ");
　　int num = Integer.parseInt(numString);
　　Combine(input， num);
　　}
　　private static void Combine(String input， int num) {
　　char a = input.toCharArray();
　　String b = "";
　　Combine(a， num， b， 0， a.length);
　　}
　　private static void Combine(char a， int num， String b， int low， int high) {
　　if (num == 0) {
　　System.out.println(b);
　　} else {
　　for (int i = low; i 《 a.length; i++) {
　　b += a;
　　Combine(a， num - 1， b， i+1， a.length);
　　b=b.substring(0， b.length()-1);
　　}
　　}
　　}
　　}

python递归算法经典实例有哪些

程序调用自身的编程技巧称为递归（ recursion）。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法。

它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

Python

是完全面向对象的语言。函数、模块、数字、字符串都是对象。并且完全支持继承、重载、派生、多继承，有益于增强源代码的复用性。Python支持重载运算符和动态类型。相对于Lisp这种传统的函数式编程语言，Python对函数式设计只提供了有限的支持。有两个标准库(functools, itertools)提供了Haskell和Standard ML中久经考验的函数式程序设计工具。

08《算法入门教程》递归算法之斐波那契数列

本节内容是递归算法系列之一：斐波那契数列递归求解，主要介绍了斐波那契数列的定义，然后用递归的实现思想分析了一下斐波那契数列，最后给出了基于 Java 代码应用递归思想实现斐波那契数列的代码实现及简单讲解。

斐波那契数列（Fibonacci sequence），也称之为黄金分割数列，由意大利数学家列昂纳多・斐波那契（Leonardo Fibonacci）提出。斐波那契数列指的是这样的一个数列：1、1、2、3、5、8、13、21、34、……，这个数列从第 3 项开始，每一项都等于前面两项之和。在数学上，斐波那契数列可以被递推的方法定义如下：

斐波那契数列是数学上面一个经典的例子，并且在日常生活中有很多应用，他还与黄金分割有着密不可分的联系，而且当 n 趋向于无穷大时，前一项与后一项的比值越来越逼近黄金分割值 0.618。

在这一节中，我们就需要利用递归的思想去求解斐波那契数列，当给出一个斐波那契中第几项的数字，然后求解出对应的斐波那契数值。在之前，我们已经定义了递归算法的相关概念，并且明确了需要应用递归时候的三要素：

接下来，我们将利用递归的知识来解决斐波那契数列问题，明确在斐波那契数列求解问题中的递归三要素分别是什么。

例如，当我们求解斐波那契数列中的 F (5) 时，按照定义，我们有：

在说明斐波那契数列的递归描述之后，我们看看如何用 Java 代码来实现对斐波那契数列的计算。

运行结果如下：

代码中的第 4 行至第 8 行分别调用斐波那契数列计算函数，计算出斐波那契数列中对应 n=1,2,3,4,5 时斐波那契数列的取值，进行结果比较，判断斐波那契数列程序实现是否正确。代码中的第 12 行至第 20 行是斐波那契数列应用递归方法进行斐波那契数列的计算，按照递归的三要素进行计算处理。

本节主要介绍了用递归思想求解斐波那契数列，在学完本节课程之后，我们了解到了什么是斐波那契数列，并且将递归算法在斐波那契数列中进行了实际应用，需要掌握斐波那契数列的递归求解方法，并自己可以实现相关的代码实现，并清楚里面的每一步逻辑。

求经典的递归算法以及案例（可用C#、PHP、J**A其中一种语言来写）!

***隐藏网址***
{
if(id==4) return 10;
else
return (AgeCal(id+1)+1);
} 【例2】计算n！【分析】虽然这道题目不像例1一样清晰明了告诉你使用“递归”法反推，但是我们有这样一个常识——n！＝(n-1)!*n；(n-1)!=(n-2)!*(n-1)……n=0或1，返回1.显然n与n-1，n-2也是线性的递减数列（等差关系）。其规律如下：F(n)=F(n-1)*nF(n-1)=F(n-2)*(n-1)F(n-2)=F(n-3)*(n-2)……F(1)=1或者F(0)=1(防止别人直接输入0)编写其递归函数，如下：int Fac(int n)
{
if(n==1 || n==0)
{
return 1;
}
else
return Fac(n-1)*n;
} 【例3】求一组整数中的最大(小)值（整数是一个int数组，个数未知）。【分析】当数字只有两个的时候，我们可以使用》和《直接比较；但是当数字超过2个的时候（假设3个），那么我们可以使用一个预订的函数（比如Max(1,2)和3进行比较），由于1，2两个数比较的时候已经得到一个最大值，因此在回代到Max中又变成了两个数的比较。这样，我们可以发现一个规律：F(1,2,3,4……n)＝F(1,2,3,4……n-1)和n比较F(1,2,3,4……n-1)＝F(1,2,3,4……n-2)和n-1比较……F(1,2,3)=F(1,2)和3比较F(1,2)＝结果（并回代）相应的递归函数如下(C#)：Code
int Max(intnumbers)
{
if(numbers.Length==2)
{
return (numbers);
}
else
{
int;
for(int i=0;i《numbers.Length-1;++i)
{
tempnumbers;
}
return (Max(tempnumbers)》numbers
}
}