【Java -- 算法】递归

定义

在数学与计算机科学中，递归(Recursion)是指在函数的定义中使用函数自身的方法。

递归的三要素：

• 明确递归终止条件
• 给出递归终止时的处理办法
• 提取重复的逻辑，缩小问题规模

递归的应用场景：

问题的定义是按递归定义的（Fibonacci函数，阶乘，…）；

问题的解法是递归的（有些问题只能使用递归方法来解决，例如，汉诺塔问题，…）；

数据结构是递归的（链表、树等的操作，包括树的遍历，树的深度，…）。

实例

1. 九九乘法表

public class Main {
public static void main(String[] args) {
method(9);
}

private static void method(int i) {
if (i == 1) {
System.out.println("1*1=1 ");
} else {
method(i - 1);
for (int j = 1; j <= i; j++) {
System.out.print(j + "*" + i + "=" + j * i + " ");
}
System.out.println();
}
}

}

2. 阶乘

public class Main {
public static void main(String[] args) {
System.out.print(method(10));
}

public static long method(int n){
if(n == 1) {
return 1;
}
return n*method(n-1);
}

}

3. 斐波纳契数列

public class Main {
public static void main(String[] args) {
System.out.print(fibonacci(1,1,8));
}

/**
* @description 经典递归法求解
*
* 斐波那契数列如下：
*
* 1,1,2,3,5,8,13,21,34,...
*
* *那么，计算fib(5)时，需要计算1次fib(4),2次fib(3),3次fib(2)，调用了2次fib(1)*，即：
*
* fib(5) = fib(4) + fib(3)
*
* fib(4) = fib(3) + fib(2) ；fib(3) = fib(2) + fib(1)
*
* fib(3) = fib(2) + fib(1)
*
* 这里面包含了许多重复计算，而实际上我们只需计算fib(4)、fib(3)、fib(2)和fib(1)各一次即可，
* 后面的optimizeFibonacci函数进行了优化，使时间复杂度降到了O(n).
*
* @author rico
* @created 2017年5月10日 下午12:00:42
* @param n
* @return
*/
public static int fibonacci(int first, int second, int n) {
if (n > 0) {
if(n == 1){ // 递归终止条件
return first; // 简单情景
}else if(n == 2){ // 递归终止条件
return second; // 简单情景
}else if (n == 3) { // 递归终止条件
return first + second; // 简单情景
}
return fibonacci(second, first + second, n - 1); // 相同重复逻辑，缩小问题规模
}
return -1;
}

}

4. 杨辉三角

public class Main {
public static void main(String[] args) {
int length = 10; // 打印的行数

for (int i = 1; i <= length; i++) {
// 打印空格
for (int j = 1; j <= length-i; j++) {
System.out.print(" ");
}
for (int j = 1; j <= i; j++) {
System.out.printf("%4d",fun(i,j));
}
System.out.println();
}
}

/**
* Title: 杨辉三角形又称Pascal三角形，它的第i+1行是(a+b)i的展开式的系数。
* 它的一个重要性质是：三角形中的每个数字等于它两肩上的数字相加。
*
* 例如，下面给出了杨辉三角形的前4行：
* 1
* 1 1
* 1 2 1
* 1 3 3 1
* @description 递归获取杨辉三角指定行、列(从0开始)的值
* 注意：与是否创建杨辉三角无关
* @author rico
* @x 指定行
* @y 指定列
*/
public static int fun(int i,int j) {
if(j == 1 || i == j) {
return 1;
}else {
return fun(i-1,j)+fun(i-1,j-1);
}
}

}

5. 回文字符串的判断

/*
* Title: 回文字符串的判断
* Description: 回文字符串就是正读倒读都一样的字符串。如”98789”, “abccba”都是回文字符串
**/
public class Main {
public static void main(String[] args) {
System.out.print(method("abccba"));
}

public static boolean method(String s) {
int start = 0;
int end = s.length()-1;
if(end > start) {
if(s.charAt(start) != s.charAt(end)){
return false;
}else{
return method(s.substring(start+1).substring(0, end-1));
}
}
return true;
}

}

【文章由香港云服务器 http://www.1234xp.com 复制请保留原URL】