java递归分析_java递归算法分析
递归算法分析：就是把复杂的问题分解为若干个相对简单的子问题，一直分解下去，直到子问题有答案为止，也就是说到了递推的出口。
递归算法要注意的两点：
(1) 递归就是在方法里调用自己;
(2) 在使用递归算法时，必须要有一个明确的递归结束条件，称为递归出口。
先看一个简单的例子，求从1加到5的和，代码如下：
package com.juziku;
/**
* 递归测试
* @author sunlightcs
* 2011-3-9
* http://hi.juziku.com/sunlightcs/
*/
public class RecursionTest {
/**
* 求从1加到n的和
*/
public static int sum(int n){
if(n == 1){
return 1;
}else{
return n + sum(n-1);
}
}
public static void main(String[] args) {
System.out.println(sum(5));
}
}
先分析一下执行的流程：
n=5时，执行sum(5)方法，返回的结果为：5 + sum(4)
n=4时，执行sum(4)方法，返回的结果为：4 + sum(3)
n=3时，执行sum(3)方法，返回的结果为：3 + sum(2)
n=2时，执行sum(2)方法，返回的结果为：2 + sum(1)
n=1时，执行sum(1)方法，返回的结果为：1
再向上返回，依次执行：
2+1
3+(2+1)
4+(3+2+1)
5+(4+3+2+1) = 15
思路应该是这样的：
要知道从1加到5的和，先得知道从1加到4的和，即：5+sum(4)
要知道从1加到4的和，先得知道从1加到3的和，即：4+sum(3)
要知道从1加到3的和，先得知道从1加到2的和，即：3+sum(2)
要知道从1加到2的和，先得知道从1加到1的和，即：2+sum(1)
从而很容易看出，递归的出口为1也就是sum(1)的值为1
递归算法分析：就是把复杂的问题分解为若干个相对简单的子问题，一直分解下去，直到子问题有答案为止，也就是说到了递推的出口。 递归算法要注意的两点： (1) 递归就是在方法里调用自己; (2) 在使用递归算法时，必须要有一个明确的递归结束条件，称为递归出口。 先看一个简单的例子，求从1加到5的和，代码如下： package com.juziku; /** * 递归测试 * @author sunlightcs * 2011-3-9 * http://hi.juziku.com/sunlightcs/ */ public class RecursionTest { /** * 求从1加到n的和 */ public static int sum(int n){ if(n == 1){ return 1; }else{ return n + sum(n-1); } } public static void main(String[] args) { System.out.println(sum(5)); } } 先分析一下执行的流程： n=5时，执行sum(5)方法，返回的结果为：5 + sum(4) n=4时，执行sum(4)方法，返回的结果为：4 + sum(3) n=3时，执行sum(3)方法，返回的结果为：3 + sum(2) n=2时，执行sum(2)方法，返回的结果为：2 + sum(1) n=1时，执行sum(1)方法，返回的结果为：1 再向上返回，依次执行： 2+1 3+(2+1) 4+(3+2+1) 5+(4+3+2+1) = 15 思路应该是这样的： 要知道从1加到5的和，先得知道从1加到4的和，即：5+sum(4) 要知道从1加到4的和，先得知道从1加到3的和，即：4+sum(3) 要知道从1加到3的和，先得知道从1加到2的和，即：3+sum(2) 要知道从1加到2的和，先得知道从1加到1的和，即：2+sum(1) 从而很容易看出，递归的出口为1也就是sum(1)的值为1