Return 递归函数

Question

了解 return 语句在 recursion

中的使用

例如在二进制搜索中：

def binary_search_recur(array,start,end,item):

    middle = int((start+end)/2)
    #print (middle)
    if (start>end):
        return -1
    else:   
        if array[middle]==item:
            return middle
        elif array[middle]>item:
            return binary_search_recur(array,start,middle-1,item)
        else:
            return binary_search_recur(array,middle+1,end,item)

用

调用函数

array = [27,45,76,81,92,101,291]
binary_search_recur(array,0,len(array)-1,27)

如果我在任何地方添加 return 语句，效果很好，但如果我删除 [=15]，它不会 return 0（示例中搜索元素的索引） =] 语句如下

else:   
      if array[middle]==item:
           return middle
      elif array[middle]>item:
           binary_search_recur(array,start,middle-1,item) #retrun statement removed
      else:
           binary_search_recur(array,middle+1,end,item)   #retrun statement removed

我的观点是，当我找到元素时，我想 return 所以我 return 索引 middle，或者如果元素根本不存在，那么在那个案例 I return -1，否则我只是用更新的 start 和 end 索引递归调用函数，就像合并排序

merge_sort(l)
merge_sort(r)
merge(l,r,array)

所以我不明白为什么删除示例中的 return 语句不会 return 操作。任何建议都会很棒。

Answer 1

循环函数的想法是return使用新参数或最终值重新执行自身。

您需要return循环中下一个方法的结果。如果不是，则 Python returns None 和内部循环函数的结果不会保存在任何地方。

Answer 2

让我们考虑以下输入

array = [0,1,2,3,4]
item = 1

您的函数执行以下步骤

start = 0, end = 4, middle = 2.

在这种情况下，在您的函数体中，您输入带有 elif array[middle]>item 的部分。然后你的递归函数使用以下输入调用第二个递归函数

start = 0, end = 1, middle = 0.

在这种情况下，您输入最后一个 else 块。然后使用以下输入调用第三个函数

start = 1, end = 1, middle = 1.

现在魔术开始了。您的函数查找 middle 和 returns 1。这会将您带回到第二个递归函数所在的行。你的第二个递归函数 returns 1 然后它带你回到你的第一个递归函数，最后它也是 returns 1。

如果删除那些 return。在这个例子中，第 1 步和第 2 步 return 什么都没有，换句话说 None.

Answer 3

递归没有什么特别之处 - 它只是简单的函数调用，函数调用自身的事实实际上完全无关紧要 - return 仅适用于和其他地方一样。

考虑一下：

def a(arg):
    return arg +1 

def b(arg):
    return a(arg * 2)

def main():
    result = b(42)
    print(result)

如果删除 b 中的 return 即：

def b(arg):
    a(arg * 2)

那么从技术上讲，您实际写的是：

def b(arg):
    a(arg * 2)
    return None

因为当它们最终没有明确的 return 语句时，Python 隐含地起作用 return None。因此，在 main() 中，result 将是 None 而不是 (arg * 2) + 1

您的代码中发生了完全相同的事情 - 如果您不明确 return 递归调用的结果（=> 再一次，事实这是一个递归调用在技术上完全不相关，它完全以相同的方式工作），你的函数将 return None，如果你写了：

    elif array[middle]>item:
        binary_search_recur(array,start,middle-1,item)
        return None
    else:
        binary_search_recur(array,middle+1,end,item)
        return None

Answer 4

关键是你必须"return the returned value"。

例如当满足以下条件时：

array[middle]>item

你的方法没有return任何东西。所以 python 将 return None 代替。

Return 递归函数

Return function in recursion

python

recursion

binary-search