黑马程序员技术交流社区

标题: Java中的递归原理分析 [打印本页]

作者: konglingzhiyu 时间: 2015-2-11 20:13
标题: Java中的递归原理分析
不是很懂递归，找了一些递归的讲解。说实话还是不是很懂。希望对大家有所帮助！解释：程序调用自身的编程技巧叫做递归。
程序调用自身的编程技巧称为递归（ recursion）。递归做为一种算法在程序设计语言中广泛应用。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。

递归的三个条件：
边界条件
递归前进段
递归返回段
当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

下面通过两个示例程序来说明：
使用Java代码求5的阶乘。（5的阶乘=5*4*3*2*1）

[java]
package org.wxp.recursion;

/**
* 计算5的阶乘(result = 5*4*3*2*1)
* @author Champion.Wong
*
*
*/
public class Test01 {
public static void main(String[] args) {
      System.out.println(f(5));
}

public static int f(int n) {
      if (1 == n)
         return 1;
      else
         return n*(n-1);
}
}

此题中，按照递归的三个条件来分析：
(1)边界条件：阶乘，乘到最后一个数，即1的时候，返回1，程序执行到底；
(2)递归前进段：当前的参数不等于1的时候，继续调用自身；
(3)递归返回段：从最大的数开始乘，如果当前参数是5，那么就是5*4，即5*(5-1)，即n*(n-1)

使用Java代码求数列：1，1，2，3，5，8......第40位的数
[java]
package org.wxp.recursion;

/**
* 求数列：1，1，2，3，5，8......第40位的数
* @author Champion.Wong
*
*/
public class Test_02_Fibonacci {
public static void main(String[] args) {
      System.out.println(f(6));
}

public static int f(int n ) {
      if (1== n || 2 == n)
         return 1;
      else
         return f(n-1) + f(n-2);
}
}

此题的突破口在：从第3位数开始，本位数是前两位数的和。要计算第多少位的值，那么就需要将位数作为参数传进方法进行计算。
(1)首先，当位数为1和2时，当前返回的值应该是1；
(2)然后，当位数为3时，返回值应该=2=1+1；
               当位数为4时，返回值=3=2+1；
               当位数为5时，返回值=5=3+2；
               当位数为6时，返回值=8=5+3；
               ......
(3)由(2)得知，大于等于3的情况下，当前位数（n）的数值=f(n-1)+f(n-2)

心得：有些初学者可能认为递归即是自己调用自己，那岂不是死循环了。对，如果递归写的不合理，那就是死循环了。但是如果写的合理，加上“边界条件”，程序执行到底的时候，会逐层返回。就像我们爬山一样，我们绕着山路爬上一层又一层，如果没有山顶，我们会一直往上爬。但如果到了山顶，就按照上山时候的步骤一层一层的往下爬。

作者: ~我思故我在~ 时间: 2015-2-11 20:57
有时候递归在编程的时候确实能起到事半功倍的效果，就是在理解程序什么时候调用，及边界的时候很难想到

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2