[数据结构与算法]递归的一种解释方式

这里借一道题目向大家解释以下递归：

给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。

实例：

输入：s = "ababbcb", k = 2
输出：5
解释：最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。

def?longestSubstring(self,?s,?k):

? ? ? ? ~~

这道题有个关键点：s中出现次数<k的字符??--->? 最后 最长字串 肯定不会包含这类字符（因为这类字符出现次数永远不会大于等于k）? ?

出现次数<k的字符 记为CH

所以我们可以 以CH 为界分割字符串，然后在分割的字符串中继续找最长的字串。

而在分割的字符串中寻找时，同样也是用到了longestSubstring()函数

那么我们便可以考虑到使用递归~~

考虑递归终止条件：

当len(s) < k 时， return 0

当找不到CH时， return lne(s)

函数编写：

def longestSubstring(self, s, k):
    if len(s) < k:
        return 0
    for ch in set(s):
        if s.count(ch) < k:
            return max(self.longestSubstring(sub, k) for sub in s.split(ch))
    return len(s)

PS：

从这道题可以看出，递归实际上就是把一个大问题分解到相同的小问题时，处理小问题时正好用到了self函数。

总之，通过上面的分析，我们看出了：我们不是为了递归而递归。而是因为我们把大问题拆解成了小问题，恰好有函数可以解决小问题，所以直接用这个函数。由于这个函数正好是本身，所以我们把此现象叫做递归。小问题是原因，递归是结果。而递归函数到底怎么一层层展开与终止的，不要用大脑去想，这是计算机干的事。我们只用把递归函数当做一个能解决问题的黑箱就够了，把更多的注意力放在拆解子问题、递归终止条件、递归函数的正确性上来。