Python을 사용하여 재귀를 이해하는 방법(코드 설명)

이 글의 내용은 Python을 사용하여 재귀를 이해하는 방법(코드 설명)에 대한 내용입니다. 필요한 친구들이 참고할 수 있기를 바랍니다.

Recursion

실행 중에 한 번 이상 호출되는 함수는 러시아 마트료시카 인형처럼 하나의 인형에 다른 인형이 포함되는 것처럼 그 자체로 재귀적입니다.

재귀는 사실 프로그래밍 언어를 배우는 과정에서 매우 빠르게 접하게 되는 부분입니다. 그러나 재귀에 대한 이해에서 누락된 부분이 있을 수 있습니다.

재귀의 분류

여기서는 재귀 호출 횟수에 따라 선형 재귀, 양방향 재귀, 다중 재귀로 구분됩니다

선형 재귀

재귀 호출이 최대 하나의 다른 재귀 호출에서 시작되면 이를 호출합니다. 선형 재귀.

예:

def binary_search(data, target, low, high):
    """
    二分查找，对有序列表进行查找，如果找到则返回True，否则返回False 
    """

    if low > high:
        return False
    else:
        mid = (low + high) // 2
        if target == data[mid]:
            return True
        elif target < data[mid]:
            return binary_search(data, target, low, mid - 1)
        else:
            return binary_search(data, target, mid + 1, high)

코드에 두 개의 bin_search가 있지만 서로 다른 조건에서 실행되며 매번 한 번만 실행할 수 있으므로 선형 재귀입니다.

양방향 재귀

한 번의 재귀 호출이 두 개의 다른 재귀 호출을 시작할 수 있다면 이를 양방향 재귀라고 부릅니다.

예:

def binary_sum(S, start, stop):
    """
    二路递归计算一个序列的和，例如S[0:5],就像切片的范围一样

    """

    if start >= stop:
        return 0
    elif start == stop - 1:
        return S[start]
    else:
        mid = (start + stop) // 2
        return binary_sum(S, start, mid) + binary_sum(S, mid, stop)

이 재귀는 실행될 때마다 함수를 두 번 호출하므로 양방향 재귀입니다. 각 재귀 후에 범위는 절반으로 줄어들므로 재귀의 깊이는 1+logn

Multiple recursion

하나의 재귀 호출이 세 개 이상의 다른 재귀 호출을 시작할 수 있다면 우리는 이를 다중 재귀라고 부릅니다.

예:

import os

def disk_usage(path):
    """
    计算一个文件系统的磁盘使用情况，

    """

    total = os.path.getsize(path)
    if os.path.isdir(path):
        for filename in os.listdir(path):
            childpath = os.path.join(path, filename)
            total += disk_usage(childpath)
    print(&#39;{0:<7}&#39;.format(total), path)
    return total

os.path.getsize는 식별된 파일 또는 디렉터리에서 사용하는 실시간 디스크 공간입니다. 제가 알기로는 식별자가 파일이면 파일의 크기를 구하고, 폴더이면 폴더의 크기를 구하지만 상자처럼 폴더의 내용은 포함하지 않는다는 것입니다. 그 안에는 많은 아이템이 있는데 여기서는 상자의 무게만 계산하고 아이템의 무게는 계산하지 않습니다. 즉, 빈 상자를 계산합니다. 따라서 이 재귀 함수의 재귀 호출 횟수는 이 수준의 파일 또는 폴더 수에 따라 달라지므로 다중 재귀입니다.

재귀의 단점

재귀의 단점은 분명히 시간과 공간의 소모입니다. 이 글에서는 캐시 방식을 사용하여 피보나치 수열의 계산 소모를 줄입니다. 그런 종류의 나쁜 재귀:

def fibonacci(n):
    """
    斐波那契数列计算，返回的是一个元组

    """

    if n <= 1:
        return (n, 0)
    else:
        (a, b) = fibonacci(n - 1)
        return(a + b, a)

원래 양방향 재귀를 선형 재귀로 변경하여 반복 계산을 줄였습니다.

Python의 최대 재귀 깊이

각 재귀는 리소스를 소비하며 각 연속 호출에는 추가 메모리가 필요합니다. 무한 재귀가 발생하면 리소스가 급격히 소모된다는 것은 명백히 비합리적입니다. 이러한 현상을 피하기 위해 Python은 의도적으로 설계 중에 재귀 깊이를 제한합니다. 994번째 호출

995번째 호출

996번째 호출

Traceback (가장 최근 호출 마지막):
파일 “D:/github/Data-Structure/code/recursive.py”, line 73, in
limitless(1)
File “ D:/github/Data-Structure/code/recursive.py”, 70행, 무한
반환 무한(n)
파일 “D:/github/Data-Structure/code /recursion.py", 70행, in limitless
returnlimitless(n)
파일 "D:/github/Data-Structure/code/recursion.py", line 70, inlimitless
returnlimitless(n)
[이전 줄이 992번 더 반복됨]
파일 "D :/github/Data-Structure/code/recursion.py", 68행, 무한
print('th' + str(n) + 'th call')
RecursionError: Python 객체를 호출하는 동안 최대 재귀 깊이가 초과되었습니다


996번에 도달하자 마침내 재귀가 멈췄습니다. 이는 Python의 재귀 깊이가 약 1000번으로 제한된다는 의미입니다.

1000개의 레이어 제한이면 충분하지만 여전히 특정 계산으로 제한될 수 있으므로 Python은 제한을 수정할 수 있는 방법을 제공합니다

import sys
def limitless(n):
    print('第' + str(n) + '次调用')
    n += 1
    return limitless(n)

print(sys.getrecursionlimit())#1000
sys.setrecursionlimit(2000)
limitless(1)

第1994次调用
第1995次调用
第1996次调用
Traceback (most recent call last):
 File “D:/github/Data-Structure/code/递归.py”, line 70, in limitless
   return limitless(n)
 File “D:/github/Data-Structure/code/递归.py”, line 70, in limitless
   return limitless(n)
 File “D:/github/Data-Structure/code/递归.py”, line 70, in limitless
   return limitless(n)
 [Previous line repeated 995 more times]
 File “D:/github/Data-Structure/code/递归.py”, line 68, in limitless
   print(‘第’ + str(n) + ‘次调用’)
RecursionError: maximum recursion depth exceeded while calling a Python objec

可见把这个深度该为2000后便多了1000次调用，但这个深度显然不是设置多少就是多少，毕竟还有计算机CPU与内存的限制，比如吧深度改为10000，那么运行后

第3920次调用
第3921次调用
第3922次调用
第3923次调用

Process finished with exit code -1073741571 (0xC00000FD)

到达3923次便终止了，查询-1073741571发现是递归栈溢出的问题。

尾递归

如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作，这个特性很重要，因为大多数现代的编译器会利用这种特点自动生成优化的代码。

Python解释器在对于一次函数调用中，会使用一个栈帧来保存当前调用的函数的信息，如输入参数、返回值空间、计算表达式时用到的临时存储空间、函数调用时保存的状态信息以及输出参数。因此在递归的调用中，这种未执行完的函数会一层一层的占用大量的栈帧。如果将递归的调用放到函数执行的最后一步，那么执行完这步，该次函数的栈帧就会释放，调用函数的新栈帧就会替换掉之前的栈帧，所以无论调用的深度有多少次，都只会占用一个栈帧，那也就不会发生栈溢出的问题。这就是尾递归。

所以根据需要，尾递归必须是线性递归，并且递归调用的返回值必须立即返回。

拿一个阶乘递归函数举例

def factorial(n):
    """
    阶乘递归函数

    """
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

上边这个是一个普通的递归，下面把他改成尾递归的形式

def facttail(n, res):
    """
    阶乘尾递归，res初始为1

    """

    if n < 0:
        return 0
    elif n == 0:
        return 1
    elif n == 1:
        return res
    else:
        return facttail(n - 1, n *res)

这个函数比之前那个还多了个res，第一种每次调用完要乘n，这里的res就起了相同的作用，由于尾递归每一层的栈帧要释放，所以通过res来作为相乘的过程。我个人认为尾递归的难度就在于参数的设计，因为它的前提条件就是调用后什么也不再执行了，所以要作为传递的东西就得提前通过参数设计传递，总之要想设计一个尾递归的算法还是需要好好思考一下的。

위 내용은 Python을 사용하여 재귀를 이해하는 방법(코드 설명)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!