So verwenden Sie Python, um die Rekursion zu verstehen (Code-Erklärung)

Der Inhalt dieses Artikels befasst sich mit der Verwendung von Python zum Verständnis der Rekursion (Code-Erklärung). Ich hoffe, dass er für Sie hilfreich ist.

Rekursion

Wenn eine Funktion während der Ausführung einmal oder mehrmals aufgerufen wird, ist sie selbst rekursiv, genau wie eine russische Matroschka-Puppe.

Rekursion ist tatsächlich etwas, mit dem Sie beim Erlernen von Programmiersprachen sehr schnell in Berührung kommen. Allerdings kann es zu einigen Lücken im Verständnis der Rekursion kommen. Lassen Sie uns dies genauer verstehen Aspekt

Klassifizierung der Rekursion

Entsprechend der Anzahl der rekursiven Aufrufe wird sie in lineare Rekursion, bidirektionale Rekursion und mehrfache Rekursion unterteilt

Lineare Rekursion

Wenn ein rekursiver Aufruf höchstens einen weiteren rekursiven Aufruf startet, nennen wir ihn lineare Rekursion.

Zum Beispiel:

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)

Obwohl der Code zwei binäre_Suchen enthält, werden sie unter unterschiedlichen Bedingungen ausgeführt und können jedes Mal nur einmal ausgeführt werden, es handelt sich also um eine lineare Rekursion.

Zwei-Wege-Rekursion

Wenn ein rekursiver Aufruf zwei andere rekursive Aufrufe starten kann, nennen wir es Zwei-Wege-Rekursion

Zum Beispiel:

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)

Diese Rekursion ruft die Funktion bei jeder Ausführung zweimal auf, daher spricht man von einer Zwei-Wege-Rekursion. Nach jeder Rekursion wird der Bereich um die Hälfte reduziert, sodass die Rekursionstiefe 1 beträgt +logn

Mehrfache Rekursion

Wenn ein rekursiver Aufruf drei oder mehr andere rekursive Aufrufe starten kann, nennen wir es multiple Rekursion

Zum Beispiel:

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 ist der Echtzeit-Speicherplatz, der von der identifizierten Datei oder dem identifizierten Verzeichnis verwendet wird. Was ich verstehe ist, dass, wenn die Kennung eine Datei ist, die Größe der Datei ermittelt wird. Wenn es sich um einen Ordner handelt, wird die Größe des Ordners ermittelt, aber der Inhalt des Ordners wird nicht berücksichtigt, genau wie bei einer Box. Es sind viele Artikel darin, aber hier wird nur das Gewicht der Box berechnet, aber das Gewicht der Artikel wird nicht berechnet, dh es wird eine leere Box berechnet. Die Anzahl der rekursiven Aufrufe in dieser rekursiven Funktion hängt also von der Anzahl der Dateien oder Ordner in dieser Ebene ab, es handelt sich also um eine Mehrfachrekursion.

Die Mängel der Rekursion

Die Mängel der Rekursion sind offensichtlich der Zeit- und Platzverbrauch. In diesem Artikel wird die Cache-Methode verwendet, um die Berechnung zu reduzieren Fibonacci-Sequenz. Hier verwenden wir eine andere Möglichkeit, die schlechte Rekursion zu verbessern:

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

    """

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

Ändern Sie die ursprüngliche Zwei-Wege-Rekursion in eine lineare Rekursion, um wiederholte Berechnungen zu reduzieren.

Maximale Rekursionstiefe von Python

Jede Rekursion verbraucht Ressourcen und jeder aufeinanderfolgende Aufruf erfordert zusätzlichen Speicher. Wenn eine unendliche Rekursion auftritt, bedeutet dies eine schnelle Erschöpfung der Ressourcen , was offensichtlich unvernünftig ist. Um dieses Phänomen zu vermeiden, begrenzt Python absichtlich die Rekursionstiefe während des Entwurfs. Wir können es testen 991. Anruf

Der 992. Anruf

Der 993. Anruf

Der 994. Anruf
Der 995. Anruf
Der 996. Anruf
Traceback (letzter Anruf zuletzt):
Datei „D: /github/Data-Structure/code/recursive.py“, Zeile 73, in
limitless(1)
Datei „D:/github/Data-Structure/code /recursive.py“, Zeile 70, in limitless
return limitless(n)
Datei „D:/github/Data-Structure/code/recursive.py“, Zeile 70, in limitless
return limitless(n)
Datei „D: /github/Data-Structure/code/recursive.py“, Zeile 70, in limitless
return limitless(n)
[Vorherige Zeile noch 992 Mal wiederholt]
Datei „D:/github/Data- Structure/code/recursion.py“, Zeile 68, in limitless
print('th' + str(n) + 'th call')
RecursionError: maximale Rekursionstiefe beim Aufrufen eines Python-Objekts überschritten


wurde schließlich auf 996 Mal rekursiert und die Rekursion gestoppt, was bedeutet, dass die Rekursionstiefe von Python auf etwa 1000 begrenzt ist.

Das Limit von 1000 Ebenen reicht aus, kann aber dennoch auf bestimmte Berechnungen beschränkt sein, daher bietet Python eine Möglichkeit, das Limit zu ändern

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来作为相乘的过程。我个人认为尾递归的难度就在于参数的设计，因为它的前提条件就是调用后什么也不再执行了，所以要作为传递的东西就得提前通过参数设计传递，总之要想设计一个尾递归的算法还是需要好好思考一下的。

Das obige ist der detaillierte Inhalt vonSo verwenden Sie Python, um die Rekursion zu verstehen (Code-Erklärung). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!