今天介绍Excel中一个非常重要的函数功能:递归。
递归就是指一个函数通过调用自身来解决问题。在Excel推出LAMBDA函数的同时,就推出了递归。我们可以创建一个递归的自定义函数,类似于:
F = LAMBDA(
x,
...
F(x-1)
...
)
为了更好地了解递归,我们先使用递归解决一个非常简单的问题:求和。
假设在单元格A2:A11区域,有一列自然数,
我们需要对它·们求和,要求你使用递归的方法。
其实,递归的思路特别符合我们的直观。整个的方法类似于这样的一段A与B之间的对话:
这段对话揭示了用递归解决问题的思路:如果你会规模小一些的问题的解决方法,那么你就可以在此基础上解决规模大一些的问题。
或者,反过来,如果你要解决规模大一些的问题,就将它们变成规模小一些的问题来处理。
写成公式是这样的:
这里,我们先计算了输入数组的长度,即行数,然后通过IF分不同情况处理:
n = 1,即数组只有一个值,不需要处理,直接返回即可
n = 2, 将数组分为两部分:最后一个元素,以及前面n-1个元素。主要解决了前面n-1个元素的和,再加上最后一个元素,就可以得到整个数组的合计。
这样,我们就将问题的规模从n变成了n-1。
不能理解,这里的分解一定不是一次性的,因为n-1还可以继续缩减规模:n-2,n-3,....,直至1。这时,就不再缩减,因为n=1时,我们会处理。
这个过程可以用下图表示:
注意,递归的函数中一定有类似于n=1的情况,即问题规模一直缩减,直至一个非常简单的情况,可以很容易就得到解,这种解我们称为平凡解。
凡治众如治寡,分数是也 —— 孙子
与其说递归是一种功能,不如说递归是一种解决问题的思路。如果知道问题规模为n-1的时候的处理方法,就可以解决规模为n的问题了。
正如孙子兵法所说,“凡治众如治寡,分数是也”。问题之所以太复杂,往往是因为规模太大引起的。为什么有些将军可以做到像管理几个人一样得心应手的管理一个大部队呢?那是因为他们使用了“分数”这种技巧。
所谓“分数”,其实就是将大规模的问题分解为更小规模的问题。
这就是使用递归时在做的事情。
所以,正确使用这种思路解决问题,你也可以做到像韩信将兵一样:多多益善。多大规模的问题对你都是轻而易举。
我们使用这种思路看一下解决字符串逆序的两种方法。
现在要将第一个字符串变成第二个字符串。
在Excel中有很多方法可以做到。但是这些方法都比递归的方法啰嗦,不直观。
我们可以这么考虑:
最上面的是原问题:给定字符串。为了解决这个问题,我们将其分解为两个问题:
右边第一个字符,这个不需要处理,是平凡的情况
左边n-1个字符,这个需要处理,但是规模已经比原来的问题规模减少了1
这就相当于问对方:你会处理n-1个字符的逆序吗?如果你会,就将结果放在右边,原来右边第一个字符放在左边!
问题解决了。
写成自定义函数就是这样的:
这个问题还可以用另外一种方式考虑:
我们拆分问题的时候,不再拆分右边一个字符,而是分成差不多相同大小的两部分:
左侧n/2个字符,问题规模减少了n/2
右侧n/2个字符,问题规模减少了n/2
依据这个思路,我们写成下面的自定义函数:
你很可能听说过一个词:分治算法。
就是将一个大问题分解为更小规模的几个小问题,然后分别解决这些小问题。这些小问题的解合起来就得到原问题的解。上面的后一种方法其实就是一种分治方法 - 分而治之。
而在对一种方法里,我们划分的两种情形实际上只有一种情形(即左边n-1个字符)需要处理,右边一个字符直接使用即可。相当于将问题规模从n缩减为n-1,所以称为减治法 - 减而治之。
其实,初学者面对递归最常见的一个疑问就是:为什么需要递归?究竟有什么实际问题需要递归来解决吗?
其实并没有!
或者说,如果你说现实中有什么数据问题需要递归来解决吗?那么答案是很少!
但是,在很多处理数据问题时,需要很多中间环节,这些环节中有一些关键点,这些关键点的解决需要用递归,或者用递归解决起来比较容易。
这里的LCS就是这样的一个问题。我自己在帮客户处理数据时就遇到过几次使用LCS的情况,都是涉及大量数据匹配的问题,比如不同人输入的门店地址写法是不同的,匹配时可以借助LCS为不同的写法赋予不同的权重,从而可以寻找最佳的匹配。
LCS - Longest Common Subsequence Problem,最长公共子串,是指给定两个字符串中出现的所有公共子串中长度最大的那个。
例如:
对字符串X和Y来说,有很多公共子串,比如A,AB,CA,CB,CBA,...,
但是长度最长的有三个:BDAB,BCAB,BCBA,其长度为4。
注:LCS不要求连续出现,只要是从左到右的顺序即可。
实际中使用LCS有两种需求,一种是找到所有的LCS;另一种是返回LCS长度即可。我们这里介绍的是后一种需求的做法。至于返回所有LCS的方法,我们以后再介绍。
下面我们分析一下解决思路。
假设给定的字符串X和Y如下:
首先确定平凡的情况。
LCS的规模涉及两个字符串的长度:m,n。仔细考虑一下就会发现,无论m=0或者n=0,问题都很简单。因为这意味着有一个字符串是空的,此时LCS应该为""。
然后考虑如何分解为更小的问题。
我们将问题分为两种情形:
Xm = Yn,即X和Y的最后一个字符是相同的
Xm ≠ Yn,即X和Y的最后一个字符是不同的
对于第一种情形,显然有以下关系:
LCS(X, Y) = LCS(LEFT(X, m-1), LEFT(Y, n-1)) & Xm
因为最后一个字符相同,所以将它去掉后,得到两个新字符串,这两个新字符串的LCS加上X的最后一个字符一定是X,Y的LCS。这个关系式将原问题(m,n)变成了规模更小的问题(m-1, n-1w)
对于第二种情形,有以下关系:
我们计算两个LCS:
LCS_A : LCS(X, LEFT(Y, n-1))
LCS_B:LCS(LEFT(X, m-1), Y)
由于X和Y最后一个字符不相同,所以,LCS_A和LCS_B中最长的那个必定是LCS(X,Y)。
因此,以长度而言:
LCS(X, Y) = MAXLENGTH(LCS_A, LCS_B)
这个关系式将原问题(m, n)变成了两个规模较小的问题(m, n-1)和(m-1, n)。
现在可以创建递归函数了:
详细解释请看视频
加入E学会,永久免费学习更多Excel应用技巧
http://www.tropic.com.cn/portal/learn/class_list
Excel+Power Query+Power Pivot+Power BI
自定义函数 底部菜单:知识库->自定义函数
面授培训 底部菜单:培训学习->面授培训
Excel企业应用 底部菜单:企业应用
也可以在历史文章中学习Excel,Power Query,Power Pivot,Power BI,Power Automate各种技巧。
联系客服