Pythonを使って再帰を理解する方法（コード解説）

この記事の内容は Python を使って再帰を理解する方法 (コードの説明) であり、一定の参考価値があります。必要な友人は参照してください。

再帰

関数が実行中に 1 回以上呼び出される場合、ロシアのマトリョーシカ人形のように、それ自体が再帰的になります。別の人形が含まれています。

再帰は、実はプログラミング言語を学習する過程ですぐに触れるものですが、理解が抜け落ちている部分もあるかもしれませんので、より深く理解しましょう。側面

再帰の分類

##ここでは再帰呼び出しの回数に応じて線形再帰、双方向再帰、多重再帰に分けられます

#線形再帰

再帰呼び出しが他の再帰呼び出しを 1 つだけ開始する場合、それを線形再帰と呼びます。

例:

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)

コード内に 2 つの binary_search がありますが、これらは異なる条件で実行され、毎回 1 回しか実行できないため、線形再帰となります。

双方向再帰

1 つの再帰呼び出しが他の 2 つの再帰呼び出しを開始できる場合、それを双方向再帰と呼びます

例:

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)

この再帰は、実行されるたびに関数を 2 回呼び出すため、双方向の再帰です。各再帰の後、範囲は半分に減少するため、再帰の深さは 1 logn

複数の再帰

#再帰呼び出しが 3 つ以上の他の再帰呼び出しを開始できる場合、それを複数の再帰と呼びます

例:

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 は設計中に再帰の深さを意図的に制限しています。

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

988 回目の呼び出し

989 回目の呼び出し

990 回目の呼び出し

991 回目の呼び出し## をテストできます。 #992 回目の呼び出し
993 回目の呼び出し
994 回目の呼び出し
995 回目の呼び出し
996 回目の呼び出し
トレースバック (最後の呼び出し):
ファイル "D:/github/Data-Structure/code/ recursive.py」、73 行目、
limitless(1)
ファイル「D:/github/Data-Structure/code /recursion.py」、70 行目、limitless
return limitless(n)
ファイル "D:/github/Data-Structure/code/recursion.py"、70 行目、制限なし
return limitless (n)
ファイル "D:/github/Data-Structure/code/ recursive.py”、70 行目、limitless の
return limitless(n)
[前の行をさらに 992 回繰り返しました]
File "D:/github/Data-Structure/code/recursion.py", 68 行目、limitless
print('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 中国語 Web サイトの他の関連記事を参照してください。