递归入门之找感觉

忘是亡心i 2023-07-13 12:15 13阅读 0赞

> 在重复中找变化，在变化中找重复！  
> 递归就是把一个问题分成一个小的子问题加上一个较大规模的问题，而较大规模的问题可以以同样的模式划分下去，直到只剩一个显而易见的小问题（我们能直接给出答案的时候）。

如果是入门者，建议看完下面的例子后回过头来好好琢磨我写的这段话。网上的有些人认为递归是3步走，我个人并不建议把算法思想固化成工厂化步骤，因为问题是千变万化的，计算机也是不断进步的，但不能取代的只有人类的思想与道德。在这里我们更是要提高自己的思维能力，保卫人类至高的智慧！ 还有一个理由就是我们不要忘记学习算法的初心，我们不是为了比赛而比赛，而是思维的开拓与提升！

1.求数组中的元素的和

> 思路：数组是不变的（完全可以放在全局里，不用写在函数参数里）；变化的是什么呢？看公式： 数组元素的和sum = arr\[0\] + f()  
> 这里f负责把去掉第一个元素之外的其他元素求和 而要求剩下n-1个数的和就要再等于arr\[1\]+f()  
> 这里f负责计算去掉前俩元素后剩下的元素的和 依此类推… 所以从哪开始切一刀，把哪个元素提出来，是变化的，因此要把索引传给函数 于是函数f  
> 应该是：

> static int f(int begin){
         
    > 	return arr[begin] + f(begin+1) 
    > }

> 那么边界条件呢？也就是什么时候结束呢？不难知道，当begin ==  
> arr.length-1的时候，也就是移到最后一个元素时，显然从该元素往后的元素之和为它本身 arr\[begin\] 因此加上边界条件：

> `if(begin == arr.length){
        
    >  	return arr[begin]; 	
    >  }`

下面是完整代码（下面的题也是一样的思路，因为都是很简单的题，就不写思路了）：

package 递归;
    
    public class 数组元素的和 {
        
    	
    	static int f(int []arr, int begin) {
        
    		if(begin == arr.length - 1) {
        
    			return arr[begin];
    		}
    		return arr[begin] + f(arr,begin+1);
    	}
    	
    	public static void main(String[] args) {
        
    		int arr[] = new int[]{
        1,2,3,4,5,5,4,3,2,1};
    		int ans = f(arr,0);
    		System.out.println(ans);
    	}
    }

2.计算阶乘

点拨：  
关系式：f(n) = n \* f(n-1);  
边界条件：0！ == 1； 1！ == 1.

package 递归;
    
    public class 阶乘 {
        
    	static int f(int n) {
        
    		if(n==0 || n==1) {
        
    			return 1;
    		}
    		return n*f(n-1);
    	}
    	
    	public static void main(String[] args) {
        
    		int ans = f(3);
    		System.out.println(ans);
    	}
    }

3.将字符串反过来  
点拨：  
关系式：从最后一个元素开始考虑切  
f(end) = str.charAt(end) + f(end-1);  
边界条件：  
当只剩第一个元素时，它的反转为它自己  
if(end == 0)  
return “”+str.charAt(end)  
(说一下为什么这里要加上一对引号，因为如果不加的话，charAt取出的是元素本身的数据类型，而函数的返回值为字符串型)

package 递归;
    /*import java.lang.String;*/
    
    public class 反转字符串 {
        
    	static String f(String str, int end) {
        
    		if(end == 0) {
        
    			return ""+str.charAt(end);
    		}
    		return str.charAt(end)+f(str, end-1);
    	}
    	public static void main(String[] args) {
        
    		String s = "abcdefg";
    		System.out.println(f(s,6));
    	}
    }

4.斐波那契数列第n项元素  
（可以思考一下哪里可以优化，是不是有大量重复的执行过程呢？请在评论区留下你的优化方法）  
点拨：  
关系式：f(n) = f(n-1) + f(n-2);  
边界条件：f(1) == 1; f(2) == 1;

package 递推;
    
    public class 斐波那契数列 {
        
    	
    	static int f(int n) {
        
    		if(n == 1 || n == 2) {
        
    			return 1;
    		}
    		return f(n-1)+f(n-2);
    	}
    	
    	public static void main(String[] args)
    	{
        
    		System.out.println(f(5));
    	}
    }

5.最大公约数

点拨：九章算术中的辗转相除法  
思路：先看个例子：8和12  
8 / 12 = 0 …8  
12 / 8 = 1…4  
8 / 4 = 2…0  
4 / 0：………over!  
从上面我们可以发现每次都是俩数相除，除数作下一次除法的被除数，余数作下一次除法的除数…直到除数为0为止，这时的被除数就是答他们的最大公约数。  
我们还可以发现 哪怕第一个数小，经过一次除法后，顺序得到交换，所以不用判断大小。  
于是：  
关系式：f(m,n) = f(n,m%n);  
边界条件：n == 0时返回答案 m  
（小贴士：m和n的最小公倍数就等于m*n再除以m和n的最大公约数，为什么呢？我给你推一下：假设m,n的最小公倍数是a，最大公约数是b，那么：m*n = (b\*(m/b)）\* n = b\* ((m/b)*n)  
而后一项相当于m和n约分后剩下的相乘，当然就是等于他们的最小公倍数a啦。所以  
m*n == a\*b恒成立

package 递推;
    
    public class 最大公倍数 {
        
    	/*
    	 * 写错名字了，是最大公约数
    	 */
    	static int f(int m, int n) {
        
    		if(n == 0) {
        
    			return m;
    		}
    		return f(n, m%n);
    	}
    	
    	public static void main(String[] args) {
        
    		 System.out.println(f(8,12));
    	}
    }

6.插入排序改递归  
思路：对数组 下标为0的-最后一个 排序  
等价于 ： 对数组的0-倒数第二个元素进行排序+ 把最后一个元素插入到前面已经排好序的数组中

package 递推;
    import java.util.Arrays;
    
    
    public class 插入排序改递归 {
        
    	
    	static void insertSort(int[]arr, int k) {
        
    		
    		if(k == 0) {
        
    			return;
    		}
    		//对前k-1个元素排序
    		insertSort(arr,k-1);
    		//把位置k的元素插入到前面的部分
    		int x = arr[k];
    		int index = k-1;
    		while(index > -1 && x < arr[index]) {
        
    			arr[index+1] = arr[index];
    			index--;
    		}
    		arr[index+1] = x;
    	}
    	public static void main(String[] args) {
        
    		int[] arr = new int[]{
        5,8,1,3,6,4};
    		insertSort(arr,5);
    		System.out.println(Arrays.toString(arr));
    	}
    }

7.汉诺塔问题

说明：  
1.  
我上面的代码里类名，包名用的汉字，希望大家不要效仿，因为我只是为了在自己的目录里一目了然，因为文件夹里项目和代码太多了，英语感觉每次找文件识别起来很麻烦。  
2.  
建议大家完成我每次在文章里留下的要求评论的要求，不仅有可能得到我的奖励，最重要的是带着你去思考联想了一次，并表达了出来，这种学习方法你将受益终身！

可以关注我的知乎哦  
[https://zhuanlan.zhihu.com/p/112318531][https_zhuanlan.zhihu.com_p_112318531]

[https_zhuanlan.zhihu.com_p_112318531]: https://zhuanlan.zhihu.com/p/112318531