从同一函数内调用函数是否安全

Question

我一直在阅读排序算法。我遇到了合并排序的这段代码：

def mergeSort(arr):

    if len(arr) > 1:

        mid = len(arr)//2

        L = arr[:mid]

        R = arr[mid:]

        #function calls itself here<<<<<<<<<<<<<<<<<<<<<<<<<

        mergeSort(L)# Sorting the first half

        mergeSort(R)# Sorting the second half

        i = j = k = 0

    

        # Copy data to temp arrays L[] and R[] 

        while i < len(L) and j < len(R):

            if L[i] < R[j]:

                arr[k] = L[i] 

                i+= 1

            else: 

                arr[k] = R[j] 

                j+= 1

                k+= 1

    

        # Checking if any element was left 

        while i < len(L): 

            arr[k] = L[i] 

            i+= 1

            k+= 1

    

        while j < len(R): 

            arr[k] = R[j] 

            j+= 1

            k+= 1

# Code to print the list 

def printList(arr):

    for i in range(len(arr)):

        print(arr[i], end =" ")

    print() 

# driver code to test the above code 

if __name__ == '__main__': 

    #arr = [12, 11, 13, 5, 6, 7]

    arr = [38, 27, 43, 3, 9, 82, 10]

    print ("Given array is", end ="\n") 

    printList(arr) 

    mergeSort(arr) 

    print("Sorted array is: ", end ="\n") 

    printList(arr) 

# This code is contributed by Mayank Khanna 

函数 mergeSort() 是从自身内部调用的，这是一个好的做法吗？我的印象是它可能会导致错误。

Answer 1

TL;DR 通常没问题，但对于某些输入可能非常危险。给定的mergeSort函数调用自身 - 这种现象称为递归。什么是递归解决问题的常见方法，其中解决方案取决于同一问题的较小实例的解决方案；比如遍历二叉树。每次递归调用都会将函数参数压入调用堆栈，并且每次调用都有自己的局部变量。递归可能会导致漏洞，例如DNS 开放递归。如果通过不定义停止条件或处理导致大量递归调用的输入而误用，则会发生堆栈溢出（这意味着调用堆栈已被使用到最大）。任何递归解决方案都可以转换为迭代解决方案（使用循环的解决方案）总结当函数调用时间合理时，递归是安全的。Python默认的递归限制是1000，所以函数调用自身不能超过1000次数。您可以使用以下方法验证它getrecursionlimit：import sys print(sys.getrecursionlimit())并将其更改为setrecursionlimit：new_recursion_limit = 1500 sys.setrecursionlimit(new_recursion_limit)递归可能并且将会导致漏洞，并且最好在处理用户输入时避免 - 有利于迭代解决方案。聚苯乙烯现在您也知道我们的网站是以什么命名的了吧！

Answer 2

在函数内部调用函数没有问题，但您必须格外小心进入无限循环。这样做的一般良好做法是仅在函数末尾调用函数（这样可以减少混淆变量值的机会）并使用某种if语句或某种意义上的语句来提供出路。