Java算法

浏览数：17 / 时间：2015年06月08日

一、递归与循环

理论上任何的循环都可以改写为递归的形式。
- 有时候因为栈的限制，需要“尾递归”（C可以用goto语句模拟尾递归）；
- java不支持尾递归。
有些语言没有循环语句，只能使用递归（LISP）。

循环改递归的关键

发现循环的逻辑相似性。
不要忘记递归“出口”。

以下是一个简单循环改造成递归的例子：

 1 /**
 2  * 采用循环的方式打印0~n
 3  */
 4 private static void print1(int n) {
 5 
 6     for (int i = 0; i <= n; i++)
 7         System.out.print(i + "\t");
 8 }
 9 
10 /**
11  * 打印从0到n【第一种递归方式】
12  */
13 private static void print2(int n) {
14 
15     if (n > 0){
16         print2(n - 1); // 打印0~n-1
17     }
18     System.out.print(n + "\t"); // 打印n
19 }
20 
21 /**
22  * 从begin打印到end【第二种递归方式】
23  */
24 private static void print3(int start, int end) {
25 
26     if (start > end)
27         return;
28     System.out.print(start + "\t");    // 打印start
29     print3(start + 1, end);            // 打印start+1~end
30 }

　　在第一种递归方式中，我们实际上应用到了“分治算法”，将问题分解为两部分：①打印0~n-1（递归处理）；②打印n（可以直接处理），先是处理的n；思考：是否可以先处理前面的内容？如果递归方法的参数仍然只有一个参数：我们首先应该处理打印0，由于没有一个相似的结构，我们无法进行下一次的递归操作——我们可以给打印方法增加一个参数（让它从start打印到end），那么该问题就可以分解为：①打印start（直接处理）；②打印start+1~end（递归处理）。