递归-虽然我不懂，但大受震撼？

发表于

递归-虽然我不懂，但大受震撼？

这是我参与11月更文挑战的第6天，活动详情查看：2021最后一次更文挑战

笔者最近在学习《数据结构与算法之美》，正好借着这个机会边练习边记录一下自己学习的知识点。今天带来的是递归。

一、什么是递归

我记得刚开始接触递归的时候，是使用递归解决汉诺塔问题，学完之后，我的感觉大概是虽然我没太懂，但我大受震撼。递归的方式去解决汉诺塔问题确实很优雅，但同时也让我觉得递归好难懂。

递归简单来说就是将一个复杂的问题拆分成类似的多个小问题，解决小问题的同时最终解决复杂问题。

举个栗子：军训报数，教官想知道这一排有多少人，就让最后一个人说让你前面的人报数，前面的人有对他前面人说让你前面的人报数，直到第一个人，他前面没人他就会知道他是第一个，报数一，后一个就会知道报数二，直到最后一个报数，教官就会知道这一排有多少人了（实际上肯定不会这么干）。从后往前传递让前面的人报数的过程就是递，从前往后依次报数的过程就是归，相信你现在对递归应该有了一个简单的认识。

二、递归满足的是三个条件

了解了什么是递归，那什么样的问题适合用递归求解呢？这里总结了三个条件：

  • 一个复杂问题可以拆分为多个子问题求解。就像报数时，我想知道我是几号我首先应该知道我前面的人是几号，而前面的人也是如此他也需要知道他前面的人是几号。
  • 这个复杂问题和子问题除了规模不相同之外，解答思路完全一致。50 个人报数和 100 个人报数除了人数不同之外，解答问题的思路是完全相同的。
  • 存在递归的终止条件。报数时，当你的前面没有人时，就是终止条件，因为这时你就是第一个，报数一。

用个简单的口诀：大拆小，无不同，有终止。当问题满足这三个条件时，使用递归的方式求解问题可能会让你事半功倍哦。

三、如何实现递归

上面我们说了这么多，但是核心问题没解决，那就是递归怎么实现或者说递归的编码怎么写？

实现递归需要将大问题分解成一个个子问题，写出递推公式和终止条件，最后将其翻译成代码。

不啰嗦，我们直接实践。

3.1 实现斐波那契数列求值

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……，从第三项开始，每一项等于前两项之和。在数学上，斐波那契数列以如下被以递推的方法定义：

f(0)=0,f(1)=1,f(n)=f(n−1)+f(n−2)f(0)=0,f(1)=1,f(n)=f(n-1)+f(n-2)f(0)=0,f(1)=1,f(n)=f(n−1)+f(n−2)
例如，求解n=5。由公式可知，f(5)=f(4)+f(3)的和，而f(4) = f(3)+f(2)，f(3)=f(2)+f(1)。f(2)=f(1)+f(0)。我们知道f(0)=0和f(1)=1，到此也无需继续分解，所以f(0)=0或f(1)=1就是递归终止的条件了。

f(5)f(4)f(3)f(3)f(2)f(2)f(1)f(1)f(0)f(2)f(1)f(1)f(0)
知道了递推公式和终止条件，将其翻译成代码，下面是具体实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
java复制代码public class FibonacciTest {
	public  static int fibonacci(int n){
		if (n== 0 || n == 1){
			return n;
		}
		return fibonacci(n-1)+fibonacci(n-2);
	}

	public static void main(String[] args) {
		System.out.println(fibonacci(12));
	}
}

3.2 实现求阶乘n!

阶乘是数学中的一种计算方式，常用于求解排列组合问题。一个正整数的阶乘是所有小于及等于该数的正整数的积，并且0的阶乘为1。

亦即n!=1×2×3×…×(n-1)×n。阶乘亦可以递归方式定义：

0!=1，n!=(n−1)!×n0!=1，n!=(n-1)!×n0!=1，n!=(n−1)!×n
例如，求解5!。我们将5！的求解一层层分解，最后分解到1！=1× 0！时，而0！=1无法继续分解了，递归就此终止。

5!=5×4!4!=4×3!3!=3×2!2!=2×1!1!=1×0!5!=5×4!\
4!=4×3!\
3!=3×2!\
2!=2×1!\
1!=1×0!\5!=5×4!4!=4×3!3!=3×2!2!=2×1!1!=1×0!
下面是具体求解代码：

1
2
3
4
5
6
java复制代码public static int factorial(int n){
	if (n == 0){
		return 1;
	}
	return n * factorial(n-1);
}

3.3 实现一组数据集合的全排列

排列，一般地，从n个不同元素中取出m（m≤n）个元素，按照一定的顺序排成一列，叫做从n个元素中取出m个元素的一个排列。特别地，当m=n时，这个排列被称作全排列。

例如：

数组{1}，全排列的结果就是{1}。

数组{1,2}，全排列的结果就是{1,2}，{2,1}。

数组{1,2,3}，全排列的结果就是{1,2,3}，{1,3,2}，{2,1,3}，{2,3,1}，{3,2,1}，{3,1,2}。

这个问题和上面的问题有些不同，它没有直接给出递推公式，但没有关系，还是一样的先进行问题分解，找出递推公式和终止条件，以数组{1,2,3}为例，看一下排列过程的实现。

先取元素1先取元素2先取元素3取元素2取元素3取元素1取元素3取元素1取元素2{ 1 , 2 , 3 }1 { 2 , 3 }2 { 1 , 3 }3 { 1 ,2 }1 , 2 { 3 }1 , 3 { 2 }1 , 2 , 31 , 3 , 22 , 1 { 3 }2 , 1 , 32 , 3 { 1 }2 , 3 , 13 , 1 { 2 }3 , 1 , 23 , 2 { 1 }3 , 2 , 1
可以看到从数组{1,2,3}中，

步骤1：先取元素1，就变成了元素1和{2,3}的全排列

步骤2：再取{2,3}中的元素2，此时变成了元素1,2和{3}的全排列，

步骤3：因为{3}只有一种排列方式，此时得到1,2,3的全排列。

在重复步骤2，再取{2,3}中的元素3，此时变成了元素1,3和{2}的全排列，因为{2}只有一种排列方式，此时得到1,3,2的全排列。

同样的，重复以上步骤，,对元素2和元素3都获取全排列。

对于n个元素也是一样，同样可以用类似上面的方式重复求出n个元素的全排列

步骤1：从n个元素中任意取一个元素x，就形成了x和n-1个元素的全排列

步骤2：为了求n-1个元素的全排列，从n-1个元素中任取一个元素y，形成x,y和n-2元素的全排列

步骤3：直到元素只剩一下一个，即只有一种全排列方式，则将这个元素放在全排列的最后一个位置，全排列结束。

这个问题的递推公式不像之前的两题可以写成具体的数学公式，而是以步骤的方式表示，且递归终止的条件就是元素只有一个时，全排列只有一种方式，则输出全排列。

下面是具体的实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
java复制代码public class Test {
	/**
	 * 求数组元素的全排列
	 */
	public static void func(int[] arr){
		func(arr,0,arr.length-1);
	}

	/**
	 * 求解数组位置 k 到位置 m 元素的全排列
	 */
	public static void func(int[] arr,int k,int m){
		if (k == m){
			//当元素只剩最后一个
			System.out.println(Arrays.toString(arr));
		}else {
			for (int i = k; i <=m ; i++) {
				swap(arr,i,k);//取位置i元素放到前面
				func(arr,k+1,m);//求 k+1 到 m 元素的排列
				swap(arr,i,k);//将之前放到前面的元素交换回来
			}
		}
	}

	/**
	 *交互数组位置 i 和位置 k 的元素
	 */
	private static void swap(int[] arr, int i , int k){
		int temp = arr[i];
		arr[i]= arr[k];
		arr[k]= temp;
	}

	public static void main(String[] args) {
		int arr[] = new int[]{1,2,3,4};
		func(arr);
	}
}

四、递归的陷阱

递归可以让我们解决问题的代码十分简洁优雅，但同时也要警惕递归存在的一些陷阱。

4.1 栈溢出

递归在编码实现时，是一个不断回调方法本身的过程，将方法一遍遍压入栈中，递归次数太多，栈就满了也即发生栈溢出。

那么怎么解决栈溢出的问题呢？

简单的解决方法一是限制递归的次数，但却不实用；二是将递归改写为循环。

4.2 重复计算

在斐波那契数列数列中求解过程中，存在着重复计算的问题。

例如求解f(5)=f(4)+f(3)的过程，在计算f(4)时，我们其实已经计算过了f(3)，但计算完f(4)后，又重复f(3)求解过程。

这里可以使用哈希表避免重复计算，将求解的中间结果存储在哈希表中，每次都先从哈希表中获取结果，没有再进行计算。

五、总结

  • 递归简单来说就是将一个复杂的问题拆分成类似的多个小问题，解决小问题的同时最终解决复杂问题。
  • 满足大拆小，无不同，有终止，这三个条件的问题就可以用递归来实现。
  • 实现递归先是分解问题，总结递推公式和终止条件，翻译成代码。找出递推公式是第一道难关，翻译成代码是第二道难关，要想破关也只能多练多用才能孰能生巧。
  • 最后要警惕递归的陷阱，栈溢出和重复计算问题。

如果你有所收获，欢迎你点赞评论，发表你对递归的想法。

你有你的想法，我有我的想法，彼此交换，我们就对递归就有了两种理解，甚至更多。

dianzanjiaxiao.jpg

往期：
队列栈链表数组

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%