首页 > 代码库 > 递归--一种直接或者间接引用自身的定义方法
递归--一种直接或者间接引用自身的定义方法
递归--一种直接或者间接引用自身的定义方法
引言:“盗梦空间”的电影。梦中梦,梦中梦,然后有时候循环。
我们在程序设计当中常常会遇到重复性的计算,我们最常用的方法是组织迭代循环,而我们除此之外还可以采用递归计算的方法。
递归的定义:递归是一种直接或者间接引用自身的定义方法。一个合法的递归一般包含俩个部分:基础部分和递归部分。
一些平时我们遇到的经典算法。
1.欧几里得递归,迭代算法
2.斐波那契数列
3.连续整数检测算法
4.逆序输出正整数的各位数
5.汉诺塔问题
6.排列产生算法
1.欧几里得递归,迭代算法
1 package com.daliu_it.arithmetic; 2 3 /** 4 * 用欧几里德算法求最大公约数 5 * 求最大公约数是一个比较基础的问题, 6 * 欧几里得早在《几何原本》中就阐明了一个高效的算法, 7 * 据说这大概发生在公元前300年左右。 8 * 具体是这样的:假设把x和y的最大公约数表示成为f(x,y), 9 * 并且x>=y>0。现在取k=x/y,b=x%y,则x=k*y+b,10 * 变形为b=x - k*y;x和y能被f(x,y)整除,那么b也能被f(x,y)整除;11 * 所以 f(x,y) = f(y,x%y)12 */13 14 public class MaxFeed {15 public int getnum(int m, int n) {16 int r = getleave(m, n);17 while (r != 0) {18 int[] s = swapnum(m, n, r);19 m = s[0];20 n = s[1];21 r = getleave(m, n);22 }23 return n;24 }25 26 /**27 * comments : 取余数28 * @param m29 * @param n30 * @return31 */32 private int getleave(int m, int n) {33 int r = m % n;34 return r;35 }36 37 /**38 * comments : 交换39 * @param m40 * @param n41 * @param r42 * @return43 */44 private int[] swapnum(int m, int n, int r) {45 m = n;46 n = r;47 int[] s = new int[2];48 s[0] = m;49 s[1] = n;50 return s;51 }52 53 /**54 * comments : 测试用例55 * @param args56 */57 public static void main(String[] args) {58 MaxFeed maxFeed = new MaxFeed();59 int r = maxFeed.getnum(96, 1000);60 System.out.println(r);61 }62 }
2.斐波那契数列
1 package com.daliu_it.arithmetic; 2 3 public class Series { 4 5 /** 6 * 题目:古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子, 小兔子长到第四个月后每个月又生一对兔子,假如兔子都不死, 7 * 问每个月的兔子总数为多少? 8 */ 9 public static void main(String[] args) {10 /*11 * 1 1 2 3 5 8 13 ....12 */13 14 int i = 0;15 for (i = 1; i <= 20; i++)16 System.out.print(f(i)+" ");17 }18 19 public static int f(int x) {20 if (x == 1 || x == 2)21 return 1;22 else23 return f(x - 1) + f(x - 2);24 }25 26 }
1 package com.daliu_it.arithmetic; 2 3 public class Series2 { 4 5 /** 6 * 题目:古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子, 小兔子长到第四个月后每个月又生一对兔子,假如兔子都不死, 7 * 问每个月的兔子总数为多少? 8 */ 9 public static void main(String[] args) {10 11 int i = 0;12 math mymath = new math();13 for (i = 1; i <= 20; i++)14 System.out.print(mymath.f(i)+" ");15 }16 17 }18 19 class math {20 public int f(int x) {21 if (x == 1 || x == 2)22 return 1;23 else24 return f(x - 1) + f(x - 2);25 }26 }
3.连续整数检测算法
4.逆序输出正整数的各位数
5.汉诺塔问题
6.排列产生算法
递归--一种直接或者间接引用自身的定义方法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。