在递归函数中保留变量的初始值

Question

我正在编写一个递归函数，它将采用两个字符串sub和string。我必须找出sub是否为string的子字符串。

递归函数是一个严格的要求，不能被删除。

这是我已经试过了，但它的破碎：

def is_substring(sub,string): 
    if sub=="": 
     return True 
    if string=="": 
     return False 
    if sub[0]==string[0]: 
     return is_substring(sub[1:],string[1:]) 
    if sub[0]!=string[0]: 
     return is_substring(sub,string[1:]) 

它返回的True代替False时：

sub='misip' 
string='mississippi' 

Answer 1

保留递归函数参数初始值的一种方法是使用其他关键字参数。通常给这个参数默认值None，所以函数的调用者不需要初始化这个参数，但是当函数递归地调用它时，它会在需要时被适当地设置。

例如：

def is_substring(sub, string, oldsub=None): 
    if sub == "": 
     return True 
    if string == "": 
     return False 

    if oldsub is None: 
     oldsub = sub 

    if sub[0] == string[0]: 
     return is_substring(sub[1:], string[1:], oldsub) 
    else: 
     return is_substring(oldsub, string[1:], oldsub) 

另一种方式来保持的值是通过定义一个包装函数内的递归函数以产生closure，像这样：

def is_substring(sub, string): 
    oldsub = sub 
    def is_substringR(sub, string): 
     if sub == "": 
      return True 
     if string == "": 
      return False 

     if oldsub is None: 
      oldsub = sub 

     if sub[0] == string[0]: 
      return is_substringR(sub[1:], string[1:]) 
     else: 
      return is_substringR(oldsub, string[1:]) 

    return is_substringR(sub, string)   

该函数执行相同算法作为早期版本。我很确定这是你试图用你的代码实现的算法。不幸的是，这个算法没有找到正确的子字符串。

所以这里是一个递归is_substring确实工作正常，但它不需要保留旧的参数值。正如我在说

def is_substring(sub, string): 
    if sub == "": 
     return True 
    if string == "": 
     return False 

    if sub == string[:len(sub)]: 
     return True 
    else: 
     return is_substring(sub, string[1:]) 

---

：

def is_substring(sub, string): 
    if sub == "": 
     return True 
    if string == "": 
     return False 

    if string.startswith(sub): 
     return True 
    else: 
     return is_substring(sub, string[1:]) 

# some tests 

data = (
    ('misip', 'mississippi'), 
    ('tle', 'cattle'), 
) 

for sub, target in data: 
    print('{!r} {!r} {}'.format(sub, target, is_substring(sub, target))) 

输出

'misip' 'mississippi' False 
'tle' 'cattle' True 

如果你不想使用.startswith方法，您可以用切片代替注释，通常的做子串测试的方法是使用in运算符，它调用字符串的.__contains__方法。

sub in string 

Answer 2

你可以添加一个参数的你的功能，从来没有改变类似：

def recur(completeString, string) : 
    if string : 
     print string 
     recur(completeString, string[:-1]) 
    else : 
     print "Nothing left from '{}'".format(completeString) 

recur("hello", "hello") 

这将输出：

hello 
hell 
hel 
he 
h 
Nothing left from 'hello' 

Answer 3

问题是，您的初始调用和稍后的调用具有稍微不同的逻辑。失败时，您的初始电话可以简单地前进至字符串中的下一个字符;您以后的电话必须从sub开始。

我为此提出了两个函数：一个包装函数，用于进行第一次比较并保留给定的界面（或者您可以更改它？），第二个函数会查找连续匹配的结尾。

下面是一个可能的解决方案，跟踪插入的print语句（和注释掉）。

def match_all(sub, string): 
    # print "ENTER ALL", sub, string 
    if sub == "": 
     # print "ALL empty sub; success" 
     return True 
    if string == "": 
     # print "ALL empty str; fail" 
     return False 
    if sub[0] == string[0]: 
     # print "ALL head match: recur" 
     return match_all(sub[1:],string[1:]) 
    else: 
     # print "ALL head diff: fail" 
     return False 

def is_substring(sub,string): 
    # print "ENTER TOP", sub, string 
    if sub == "": 
     # print "empty sub; success" 
     return True 
    if string == "": 
     # print "empty str; fail" 
     return False 
    if sub[0] == string[0]: 
     # print "head match: recur" 
     if match_all(sub[1:],string[1:]): 
      return True 
    # print "head diff: recur" 
    return is_substring(sub,string[1:]) 

print is_substring("misip", "mississippi") 
# print "------------" 
print is_substring("sip", "mississippi") 

请注意，逻辑更改：主函数查找即时结果，但如果找不到此类解决方案仍会继续。支持函数只在该字符串位置处立即匹配。