递归算法及经典递归例子代码实现

11634029 贡献于2017-03-09

作者 ferrit3614  创建于2017-03-08 14:19:00   修改者ferrit3614  修改于2017-03-08 15:00:00字数4735

文档摘要:递归算法是一种直接或者间接调用自身函数或者方法的算法,我们就可以利用大道至简的思想,把一个大的复杂的问题层层转换为一个小的和原问题相似的问题来求解的这样一种策略。递归往往能给我们带来非常简洁直观的代码 ,从而使我们的编码大大简化,然而递归的思维确实很我们的常规思维相逆的,我们通常都是从上而下的思维问题, 而递归趋势从下往上的进行思维。这样我们就能看到我们会用很少的语句解决了非常大的问题,所以递归策略的最主要体现就是小的代码量解决了非常复杂的问题。
关键词:

1 递归算法及经典递归例子 递归(recursion):程序调用自身的编程技巧。   递归满足2个条件:     1)有反复执行的过程(调用自身)     2)有跳出反复执行过程的条件(递归出口)  递归算法是一种直接或者间接调用自身函数或者方法的算法,我们就可以利用大道至简的思想,把一个大的复杂的问题层层转换为一个小的和原问题相似的问题来求解的这样一种策略。递归往往能给我们带来非常简洁直观的代码 ,从而使我们的编码大大简化,然而递归的思维确实很我们的常规思维相逆的,我们通常都是从上而下的思维问题, 而递归趋势从下往上的进行思维。这样我们就能看到我们会用很少的语句解决了非常大的问题,所以递归策略的最主要体现就是小的代码量解决了非常复杂的问题。 递归算法解决问题的特点: 1)递归就是方法里调用自身。 2)在使用递增归策略时,必须有一个明确的递归结束条件,称为递归出口。 3)递归算法解题通常显得很简洁,但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。 4)在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等,所以一般不提倡用递归算法设计程序。 在做递归算法的时候,一定要把握住出口,也就是做递归算法必须要有一个明确的递归结束条件。这一点是非常重要的。其实这个出口是非常好理解的,就是一个条件,当满足了这个条件的时候我们就不再递归了。 递归算法一般用于解决三类问题: (1)数据的定义是按递归定义的。(Fibonacci函数) (2)问题解法按递归算法实现。(回溯) (3)数据的结构形式是按递归定义的。(树的遍历,图的搜索) 递归的缺点: 递归算法解题的运行效率较低。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。 递归与迭代都是基于控制结构:迭代用重复结构,而递归用选择结构。 递归例子: (1)阶乘 n! = n * (n-1) * (n-2) * ...* 1(n>0) //阶乘 int recursive(int i) { int sum = 0; if (0 == i) return (1); else sum = i * recursive(i-1); return sum; } (2)汉内塔问题 //汉内塔 void hanoi(int n,int p1,int p2,int p3) { if(1==n) cout<<"盘子从"< 1)    return Fib(n-1) + Fib(n-2); }   (4)判定一系列字符串中是否有相同的内容 public class T { public static void main(String[] args) { String[] a = {"a1","a2","a3","b3","c","b","33","33"}; boolean b = new T().fun(0, a); System.out.println(b); } public boolean fun(int n,String[] a){ boolean b = false; if(n == a.length){ b = true; }else{ for(int i = n; i < a.length-1; i++){ System.out.println(n+" "+(i+1)); if(a[n].equals(a[i+1])){ return false; } } n++; fun(n,a); } return b; } } (5)求数组中的最大值 用递归算法求数组中的最大值。 /** * 用递归算法求数组中的最大值 * @param a 数组 * @param low 数组下标 * @param heigh 数组上标 * @return */ public static int Max(int[] a, int low, int heigh) { int max; if(low > heigh-2) { if(a[low] > a[heigh]) max = a[low]; else max = a[heigh]; }else { int mid = (low + heigh)/2; int max1 = Max(a, low, mid); int max2 = Max(a, mid+1, heigh); max = max1>max2 ? max1 : max2; } return max; } (6) 数字塔问题 用递归算法求解数字塔问题。 n=1时 1 n=2时 1       2      2       n=3时 1       2      2       3      3      3    n=4时 1       2      2       3      3      3       4      4      4      4    /** * 用递归算法求解数字塔问题 * @param n 数字塔的行数 * @return 数字塔的字符串 */ public static String tourData(int n) { String str = new String(); if(1 == n) { str = rowData(n) + "\n"; return str; } else { str = tourData(n-1) + rowData(n) + "\n"; } return str; } private static String rowData(int n) { String str = new String(); for(int i=0; i

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 10 金币 [ 分享文档获得金币 ] 0 人已下载

下载文档