数据结构与算法简述递归算法

港控/mmm° 2022-03-31 13:58 287阅读 0赞

递归就是函数（方法）不断调用自身，直到得到想要的结果。

其思路是把一个大问题转化为规模很小的子问题，这些子问题性质一样，可以采用同一种方式处理，通过解决小问题来达到解决大问题的目的。

典型使用递归的有计算阶乘，汉诺塔问题等，递归有三要素：1明确的终止条件，不能一直递归下去，2终止处理办法，3能提取重复的逻辑，简单化问题。

计算阶乘

/**
     * 递归
     * 阶乘
     */
    public class Factorial {
    
    	/**
    	 * 计算n的阶乘
    	 */
    	public int factorial(int n) {
    		if(n == 1) {
    			return 1;
    		}
    		return n * factorial(n-1);
    	}
    	
    	public static void main(String[] args) {
    		Factorial f = new Factorial();
    		System.out.println(f.factorial(4));
    	}
    }

**汉诺塔问题**

源于印度古老历史，三根柱子，有n个从小到大的圆盘放在一根柱子上，把所有圆盘移动到另外一个柱子上，并且有如下要求，每次只能移动一个，大圆盘不能在小圆盘之上，移动完之后状态和最初状态一直，上到下是从小到大的次序。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyODEyNDYyNDA_size_16_color_FFFFFF_t_70][]

使用递归的分而治之思想来解决问题，假设A柱有n个盘子，先把较小n-1个盘子当成一个整体转移到B柱，再把最后一个盘子移到C柱，依次递归循环下去，C柱为目标柱dest，A和B依次为源柱、临时柱，动态切换

代码实现

/**
     * 递归实现汉诺塔
     */
    public class Towers {
    	
    	/**
    	 * 汉诺塔
    	 * @param topN  待移动圆盘数量
    	 * @param src 	源头柱
    	 * @param temp	临时柱
    	 * @param dest	目标柱
    	 */
    	private static void transfer(int topN, String src, String temp, String dest) {
    		if(topN == 1) {
    			System.out.println(topN + "从" + src + "移动到" + dest);
    		} else {
    			//把topN-1当成整体，移动到temp柱上
    			transfer(topN-1, src, dest, temp);
    			//把最大盘移到dest柱上
    			System.out.println(topN + "从" + src + "移动到" + dest);
    			//把topN-1移动到dest柱上
    			transfer(topN-1, temp, src,  dest);
    		}
    	}
    	
    	public static void main(String[] args) {
    		transfer(6, "A", "B", "C");
    	}
    }

**背包问题**

给定一些大小不一的物品和一个一定容量的背包，如何选择物品把背包刚好装满

/**
     * 背包问题
     */
    public class Bags {
    
    	public static void bags(int target,int[] t,int nowIndex,List<Integer> result) {
    		
    		if(nowIndex > t.length-1) {	//终止递归
    			return;
    		}
    		
    		if(t[nowIndex] > target) {	//物品比背包大，直接略过
    			bags(target, t, nowIndex + 1, result);
    		}else if(t[nowIndex] < target){	//物品小于背包，把物品放入背包，减小空余容量，轮询下一物品
    			result.add(t[nowIndex]);
    			bags(target-t[nowIndex], t, nowIndex+1, result);
    		}else{	//物品和背包空余容量大小相等，背包刚好装满，输出结果
    			result.add(t[nowIndex]);
    			System.out.println(result.toString());
    		}
    	}
    	
    	public static void main(String[] args) {
    		int[] t = {11,8,7,5,20,6,9,7};
    		for (int i = 0; i < t.length; i++) {
    			bags(20, t, i, new ArrayList<>());
    		}
    	}
    	
    }

结果\[8, 7, 5\]、\[5, 6, 9\]、\[20\]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyODEyNDYyNDA_size_16_color_FFFFFF_t_70]: /images/20220331/e12d3f865f0e4c899e697b46d3c31bba.png