首页 > 代码库 > 递归--一种直接或者间接引用自身的定义方法

递归--一种直接或者间接引用自身的定义方法

递归--一种直接或者间接引用自身的定义方法

     引言:“盗梦空间”的电影。梦中梦,梦中梦,然后有时候循环。

     我们在程序设计当中常常会遇到重复性的计算,我们最常用的方法是组织迭代循环,而我们除此之外还可以采用递归计算的方法。

递归的定义:递归是一种直接或者间接引用自身的定义方法。一个合法的递归一般包含俩个部分:基础部分和递归部分。

      一些平时我们遇到的经典算法。

          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.排列产生算法

 

递归--一种直接或者间接引用自身的定义方法