Comment utiliser Python pour comprendre la récursivité (explication du code)

Le contenu de cet article explique comment utiliser Python pour comprendre la récursivité (explication du code). Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.

Récursion

Lorsqu'une fonction est appelée une ou plusieurs fois lors de l'exécution, elle est elle-même récursive, tout comme une poupée matriochka russe contient une autre poupée.

La récursion est en fait quelque chose avec lequel vous entrerez en contact très rapidement dans le processus d'apprentissage des langages de programmation. Cependant, il peut y avoir quelques omissions dans la compréhension de la récursivité. Comprenons cela plus en profondeur. aspect

Classification de la récursion

Selon le nombre d'appels récursifs, elle est divisée en récursion linéaire, récursion bidirectionnelle et récursion multiple

Récursion linéaire

Si un appel récursif démarre au plus un autre appel récursif, nous appelons cela récursion linéaire.

Par exemple :

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)

Bien qu'il y ait deux recherches binaires dans le code, elles sont exécutées dans des conditions différentes et ne peuvent être exécutées qu'une seule fois à chaque fois, il s'agit donc d'une récursion linéaire.

Récursion bidirectionnelle

Si un appel récursif peut démarrer deux autres appels récursifs, nous appelons cela récursion bidirectionnelle

Par exemple :

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)

Cette récursion appellera la fonction deux fois à chaque fois qu'elle est exécutée, il s'agit donc d'une récursion bidirectionnelle. Après chaque récursion, la plage est réduite de moitié, donc la profondeur de la récursion est de 1+. logn

Récursion multiple

Si un appel récursif peut démarrer trois autres appels récursifs ou plus, nous l'appelons récursion multiple

Par exemple :

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 est l'espace disque en temps réel utilisé par le fichier ou le répertoire identifié. Ce que je comprends, c'est que si l'identifiant est un fichier, alors la taille du fichier est obtenue. S'il s'agit d'un dossier, la taille du dossier est obtenue, mais le contenu du dossier n'est pas inclus, tout comme une boîte. De nombreux éléments y sont placés, mais seul le poids de la boîte est calculé ici, mais le poids des éléments n'est pas calculé, c'est-à-dire qu'une boîte vide est calculée. Ainsi, le nombre d'appels récursifs dans cette fonction récursive dépend du nombre de fichiers ou de dossiers à ce niveau, il s'agit donc d'une récursion multiple.

Les défauts de la récursion

Les défauts de la récursivité sont évidemment la consommation de temps et d'espace. Dans cet article, la méthode du cache est utilisée pour réduire le calcul du. Séquence de Fibonacci. Consommation, nous utilisons ici une autre façon d'améliorer la mauvaise récursion :

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

    """

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

Changer la récursion bidirectionnelle d'origine en récursivité linéaire, réduisant ainsi les calculs répétés.

Profondeur de récursion maximale de python

Chaque récursion consommera des ressources, et chaque appel consécutif nécessitera de la mémoire supplémentaire. Lorsqu'une récursion infinie se produit, cela signifie un épuisement rapide des ressources. , ce qui est évidemment déraisonnable. Afin d'éviter ce phénomène, python limite intentionnellement la profondeur de récursivité lors de la conception. Nous pouvons le tester

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

Le 988ème appel
Le 989ème appel
Le 990ème appel appel<.>991e appel
992e appel
993e appel
994e appel
995e appel
996e appel
Traceback (dernier appel le plus récent) :
Fichier « D :/github/ Data-Structure/code/recursive.py", ligne 73, dans
limitless(1)
Fichier "D:/github/Data-Structure /code/recursive.py", ligne 70, dans limitless
return limitless(n)
Fichier « D:/github/Data-Structure/code/recursive.py », ligne 70, dans limitless
return limitless(n)
Fichier « D:/github/ Data-Structure/code/recursive.py", ligne 70, dans limitless
return limitless(n)
[Ligne précédente répétée 992 fois de plus]
Fichier "D:/github/Data-Structure/code /recursion.py", ligne 68, en illimité
print('th' + str(n) + 'th call')
RecursionError : profondeur de récursion maximale dépassée lors de l'appel d'un objet Python

a finalement récurci jusqu'à 996 fois et a arrêté la récursion, ce qui signifie que la profondeur de récursion de python est limitée à environ 1000.

La limite de 1000 couches est suffisante, mais elle peut quand même être limitée à certains calculs, donc python fournit un moyen de modifier la limite

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!