在非负集定义一个函数f，满足f(0) = 0 且 f(x) = 2f(x-1) + x^2，可以看出f(1) = 1,f(2) = 6,f(3) = 21，当一个函数用自己来定义时就称为递归函数，java中允许函数递归
1 public int f(int x){ 2 if(x == 0){ 3 return 0; 4 }else{ 5 int b = 2*f(x-1)+ x*x; //递归调用 6 return b; 7 } 8 }
递归是一种循环推理，例如我们想得到f(4)的值，那么第6行要计算2*f(3)+4*4，得到f(3)需要计算2*f(2)+3*3，得到f(2)需要计算2*f(1)+2*2，计算f(1)需要计算2*f(0)+1*1，f(0) = 0是已知基准情况，从而得出结果f(1) = 1，f(2) = 6，f(3) = 21，f(4) = 58，这样的情况就是循环推理。
递归的基本法则：基准情形，不用递归就可以求解
不断推进，递归调用总能向着一个基准情形前进
设计法则，假设所有递归调用都能运行
合成效益法则，求解一个问题的同一实例时，切勿在不同的递归调用中做重复的工作
2、实践
（1）求和：1+2+3+.....+n
/**
* 求和,程序实现是从基准情形f(0) =0逆序相加，0+1+2+3+.....+(n-1)+n
* @param n
* @return
*/
public int f1(int n){
int b = 0;
if(n == 0 ){
return 0;
}else {
b = n + f1(n-1);
return b;
}
}
（2）阶乘：n! = n * (n-1) * (n-2) * ...* 1(n>0)
/**
* 阶乘，程序实现是从基准情形f(1) =1逆序相乘，1*2*3*4*.....*(n-1)*n
* @param n
* @return
*/
public int f2 (int n){
int b = 0;
if( n == 1){
return 1;
}else {
b = n * f2(n-1);
}
return b;
}
（3）河内塔问题：
借助2号杆把1号杆上的珠子转移到3号杆上且顺序不变，一次只能移动一个珠子且大珠子不能在小珠子上面，最少需要移动多少次？
/**
* 河内塔问题，最少移动2^n-1次，f3(1) = 1,f(2) = 3,f(3) = 7,f(4) = 15
* 假如只有1个穿孔圆盘，就需要移动1次。 A→C 1 次
* 假如只有2个穿孔圆盘，就需要移动3次。A→B， A→C，B→C 3次
* 假如只有3个穿孔圆盘，这时我们可以将上面的2个圆盘看做是一个整体，也就是将3分解成1+2.来考虑。
* 如我们将最大的第三个圆盘，取消，只剩2个圆盘，这时借助C柱，移动3次可以让2个圆盘到从A到B柱。再考虑最大的圆盘，移动最大的第三个圆盘到C柱。这时借助A柱，移动3次可以让2个圆盘从B到C柱。就需要移动7次。
* @param n
* @param a 1号柱
* @param b 2号柱
* @param c 3号柱
*/
public void f3(int n, String a, String b, String c) {
if(1 == n) {
System.out.println(a + "->" + c);
}
else{
f3(n-1, a, c, b);
System.out.println(a + "->" + c);
f3 (n-1, b, a, c);
}
}
public int f3_1(int n){
int b = 0;
if(n == 1){
return 1;
}else{
b = 2*f3_1(n-1)+1;
return b;
}
}
（4）斐波那契数列：1、1、2、3、5、8、13、21、……
/**
*斐波那契数列，n=1和n=2两种基准情形，n=3开始，后一个数等于前两个数相加的和，f4(3) = f(2) + f(1)
* @param n
* @return
*/
public int f4(int n){
int b = 0;
if (n ==1 ){
return 1;
}else if(n == 2){
return 1;
}else {
b = f4(n-1)+f4(n-2);
return b;
}
}
（5）全排列：从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。
如1,2,3三个元素的全排列为：1,2,3、1,3,2、2,1,3、2,3,1、3,1,2、 3,2,1
/**
* 全排列，对数组中的数进行循环换位，输出
* @param arr 输入数组
* @param start 起始位置
* @param end 结束位置,arr.length-1
* @return
*/
public void f5(int[] arr, int start, int end){
// 递归终止条件
if (start == end) {
//循环遍历
for (int i : arr) {
System.out.print(i);
}
System.out.println();
return;
}
for (int i = start; i <= end; i++) {
swap(arr, i, start);
f5(arr, start + 1, end);
swap(arr, i, start);
}
}
private void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
/**
*全排列的数量，就是数组长度的阶乘，n=1 num=1,n=2 num=1*2=2,n=3 num =1*2*3=6;n=4 num=1*2*3*4=21.......
* @param arr
* @return
*/
public int f5_1(int[] arr){
int num = 0;
num = f5_1_1(arr.length);
return num;
}
public int f5_1_1(int n){
if(n == 1){
return 1;
}else{
return n * f5_1_1(n-1);
}
}