递归与递归算法实例（java实现）

 一、递归介绍

        递归算法（英语：recursion algorithm）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。绝大 多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。

        定义： 一个方法在执行过程中调用自身, 就称为 “递归”。

如下图是递归算法的经典实例——hanoi塔问题

二、递归算法实例 

1、猴子吃桃：猴子第一天摘了若干个桃子，当即吃了一半，还不解馋，有多吃了一个；第二天，吃剩下的桃子的一半，还不过瘾，有多吃了一个；以后每天都吃前一天剩下的一半多一个，到第10天想再吃时，只剩下一个桃子了。问第一天共摘了多少个桃子？

public static void main(String[] args) {
        int peach = peach(1);
        System.out.println(peach);
    }

    /**
     * @param n 第几天
     * @return
     */
    public static int peach(int n){
        if(n == 10){
            return 1;
        }
        return (peach(n + 1) + 1) * 2;
 }

运行结果：

 2、不死神兔：一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死，那么一年以后可以繁殖多少对兔子？

案例分析：

• 第一个月小兔子没有繁殖能力，所以还是一对；

• 两个月后，生下一对小兔子，总数共有两对；

• 三个月以后，老兔子又生下一对，因为小兔子还没有繁殖能力，总数共是三对；

• 依次类推。

思路：

• 这个数列的第1和2项属于固定值，F(1)=1，F(2)=1,；

• 从第三项开始，F(n)=F(n - 1)+F(n - 2)，可以使用递归实现，并要有一个出口；

public class FibonacciSequenceTest {
	public static void main(String[] args) {
		// 调用方法，获取12个月后的对数
		int total =fun(12);
		
        System.out.println("一年后兔子总对数是："+total);
	}
	// 定义递归放获取对应月数的兔子总对数
	public static int fun(int m){
		if(m==1 || m==2) {
			return 1;
		}else {
			// 递归调用，求取前2个月对数之和
			return fun(m-1)+fun(m-2);
		}
	}
}

运行结果：

 3、小球落地：小球从100米高空落下，每次弹起高度为原来的一半，问第10次小球落地，小球共经过多少米？

public static void main(String[] args) {
        double height = height(10, 100);

        System.out.println(height);
    }

    /**
     *
     * @param n : 第几次落地
     * @param length : 初始高度
     * @return
     */
    public static double height(int n,double length){
        if (n == 1){
            return 100;
        }
        return length + height(n - 1,length / 2);
 }

运行结果：

4、递归实现二分查找

public class BinarySearchTest {
	 public static void main(String[] args) {
		 // 定义一个有序数组 
		 int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
		 // 调用递归算法查找元素位置
		 int key=4;
		 int index= binSearch(arr, 0, arr.length-1, key);
		 // 输出结果
		 System.out.println(key+"数字在数组的角标位置是："+index);
	 }
	 // 定义递归二分算法
 	 public static int binSearch(int arr[], int start, int end, int key) {
 		 int mid = start + (end - start) / 2;
 		 // 找到对应元素
 		 if (arr[mid] == key) {
 			 return mid;
		 }
 		 if (key > arr[mid]) {
 			 // 递归调用二分查找
 			 return binSearch(arr, mid + 1, end, key);
		 } else if (key < arr[mid]) {
			 // 递归调用二分查找
			 return binSearch(arr, start, mid - 1, key);			
		 }
 		 // 没有找到，返回-1标志
 		 if (start >= end) {
 			 return -1;
 		 }
 		 return -1;
     }
}