例示的再帰

微信公衆番号:Python に注目し、より多くの実戦文章を学ぶ.
問題を考える
文章が正式に始まる前に、1元、2元、5元、10元の4種類の紙幣を与えて、どのように組み合わせ(1枚の紙幣の使用回数を制限しない)を通じて12元の商品を購入しますか?ソート順を考慮しない場合、どのような組み合わせがありますか?配列順を考えると、どれだけの可能な組み合わせがありますか?例えば1元札10枚.Pythonを使ってこのような問題を解決してみてください.文章の終わりに、私は自分の思考結果を提供します.
よく知っている例
生活の中で、多くの再帰の例があって、私达は再帰を学ぶ时、生活の中の例をプログラミングの言语の実现に転化するのが上手です.このようにプログラミングの思考を鍛えて、また自分の概念に対する理解を深めました.
例えば、みんなはこの话を闻いたことがあるでしょう:昔山があって、山の上に寺があって、寺の中にお坊さんがいて、お坊さんはストーリを话してお坊さんに闻きました:昔山があって、山の上に寺があって、寺の中にお坊さんがいて、お坊さんはストーリを话してお坊さんに闻きました:昔山があって、山の上に寺があって、寺の中にお坊さんがいて、お坊さんはストーリを话してお坊さんに闻きます
これが無限再帰の物語です.では、Pythonの説明をどのように使うべきでしょうか.
まず、再帰関数とは何かを見てみましょう.1つの関数がその内部で関数自体を呼び出し、この関数を再帰関数と呼びます.次のコードを簡単に書くことができます.

story = '     ，     ，       ，            :'
def recursive(story=story):
    return story + recursive(story)

このようにするのは明らかにだめだ.関数はスタックがオーバーフローするまで無限に再帰され、コンパイラはエラーを報告します:maximum recursion depth exceeded.停止条件が欠けているため、recursive関数が呼び出しを続行するのではなく、戻り値を取得できるタイミングが欠けています.

story = '     ，     ，       ，            :'
count = 0
def recursive(story=story):
    global count
    #     
    if count == 120:
        return story
    count += 1
    return story + recursive(story)

今回は停止条件を設定します.count=120、つまり、関数が呼び出されるたびにcount値に1を加算します.count値が120の場合、呼び出し自体を停止し、storyを返します.最後に121個のstory文字列を加算した結果を得た.
これは可能ですが、すべての文字列を印刷するのではなく、グローバル変数countを使用するのではありません.関数をclassに書き換えます

class Template:
    def __init__(self):
        self.string = '     ，     ，       ，            :'
     
    def _recursive(self, s):
        #     
        if self.count == 120:
            return s
        self.count += 1
        return s + self._recursive(s)
    
    @MyRepr
    def recursive(self):
        #   
        self.count = 0
        return self._recursive(self.string)
   
    def __repr__(self):
        return self.recursive()

MyReprアクセサリーは標準ライブラリreprlibに対してです.Reprクラスの書き換え:

from functools import partial

class MyRepr(Repr):
    def __init__(self, cls):
        super().__init__()
        #          
        self.maxstring = 100
        self.cls = cls      
        
    def __call__(self, *args, **kwargs):
        text = self.cls(*args, **kwargs)
        return self.repr(text)
      
    def __get__(self, instance, cls):
        return partial(self, instance)

このように出力文字列の長いはselfである.maxstringは引き継ぎ、MyReprは文字列の長さを100に限定し、文字列の間に省略符を付け、出力スタイルは以下の通りである.

'     ，     ，       ，            :     ，     ，  ... ，            :     ，     ，       ，            :'

Pythonでの再帰
再帰は両刃の剣だ.サイクルよりも分かりやすく、論理的に明確ですが、システムリソースを大量に消費します.Pythonも再帰層数に制限があり,テール再帰最適化はサポートされていない.
しかし、再帰を使用すると、問題を迅速に解決することができます.特に、リソースに対する要求が大きくない問題があります.再帰は、考え方を整理してから、ループを使用して再帰を書き換えることもできます.特に複雑な問題があり,再帰以外の解決策を見つけるのは難しい.
Pythonインタラクションモードでは、システムがサポートする再帰層の数を表示したい場合は、次のように入力します.

>>> import sys
>>> sys.getrecursionlimit()
3000

練習の小例
以下の小さな例を自分で持って、再帰的な実現を使って手を練習することができます.私が書いたコードは参考にするだけで、必ずしも最適な解法ではありません.もっと良い解法があれば、伝言アプリに貼ってもいいです.

階乗n!=n x (n−1) x (n−2) x (n−3) ⋅⋅⋅⋅ x 3 x 2 x 1!

シーケンスとseq=[1,5,7]sum=1+5+7

を求める

シーケンス最大値seq=[1,5,2,7,8]max=8

を求める

再帰版クイックソート

>>> seq = [9, 8, 7, 6, 5, 4, 3]
>>> random.shuffle(seq)
>>>seq
[6, 4, 9, 3, 8, 5, 7]
>>> quicksort(seq)
>>> [3, 4, 5, 6, 7, 8, 9]

フィボナッチ関数Fn=Fn-1+Fn-2

階乗
n! = n x (n−1) x (n−2) x (n−3) ⋅⋅⋅⋅ x 3 x 2 x 1!
停止条件:n<2

def factor(n):
    # assert n >= 0
    if n < 2:
        return 1
    return n * factor(n-1)

シン:

#    n >= 0
def factor(n):
    return 1 if n < 2 else n * factor(n-1)

シーケンスと
seq = [1, 5, 7] sum = 1 + 5 + 7
停止条件:シーケンスがNULL

#  
def naive_sum(seq):
    if not seq:
        return 0
    else:
        return seq[0] + naive_sum(seq[1:])

シーケンスの最大値を求める
seq = [1, 5, 2, 7, 8] max = 8
停止条件:シーケンスがNULL

#    
count = 1
def naive_max(seq):
    global count
    global max_num
    if count:
        max_num = seq[0]
        count = 0
    if not seq:
        count = 1
        return max_num
    else:
        if seq[0] > max_num:
            seq[0], max_num = max_num, seq[0]
        return naive_max(seq[1:])

高速ソートは、アルゴリズムが最悪の時間的複雑さに陥らないように、まずシーケンスの順序を乱す必要があります.クイックソートは、「分割」メソッドを使用します.一連のシーケンスについては、まずその中から1つの数を選択し、この数より小さい値は左側に積み重ねられ、この数より大きい値は右側に積み重ねられる.次に、左右の積み重ねをすばやく並べ替え続けます.クイックソートを行うシーケンスの長さが2未満になるまで(シーケンスに1つの値または空の値しかありません).
注意:再帰版のスナップショットはリソースを消費します.

# quicksort
import random
def quicksort(seq):
    if len(seq) < 2:
        return seq
    else:
        base = seq[0]
        left = [elem for elem in seq[1:] if elem < base]
        right = [elem for elem in seq[1:] if elem > base]
        return quicksort(left) + [base] + quicksort(right)
seq = [9, 8, 7, 6, 5, 4, 3]
random.shuffle(seq)
# seq：[6, 4, 9, 3, 8, 5, 7]
print(quicksort(seq))
#   ：[3, 4, 5, 6, 7, 8, 9]

フィボナッチ関数:
Fn = Fn-1 + Fn-2
停止条件:n<2
ここではlru_を使いましたCache結果をキャッシュし、lru_Cacheは呼び出し関数の結果を辞書に保存し、関数を呼び出すたびに、まず辞書に呼び出し結果があるかどうかをクエリーします.ある場合、関数は再帰を続ける必要はなく、この結果を返します.maxsizeはNoneで、キャッシュセットサイズに上限がないことを示します.
例えばfibonacci(20)は段階的に再帰し、fibonacci(1)、fibonacci(2)......を何度も呼び出すほど、これらの結果を保存し、同じ関数を繰り返し計算する必要がなく、再帰がより多くのデータを処理できるようにします.

from functools import lru_cache

@lru_cache(maxsize=None)  
def fibonacci(n:int) -> int:
    if n < 2:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

冒頭の質問
冒頭の質問に戻ります:1元、2元、5元、10元の4種類の紙幣を与えて、どのように組み合わせ(1枚の紙幣の使用回数を制限しない)を通じて12元の商品を購入しますか?
標準ライブラリdoctestを使用したテストの内容は、1番目のlenは、結果に対する配列順序の影響を考慮し、2番目のlenは、結果に対する配列順序の影響を考慮しないことです.第1の方式は、377種類の可能な組み合わせがある.第2の方法は、11の可能な組み合わせがある.

>>> currency = {1, 2, 5, 10}
>>> value = 12
>>> len(equal(currency, value))
377
>>> len(equal(currency, value, dup=True))
11

まず停止条件1を決定し、紙幣の総額が12元に達した場合、再帰は停止し、可能な組み合わせを返すべきである.停止条件2は、紙幣の総額が12元を超える場合、再帰も停止し、空のリストを返すべきである.
紙幣リストcurrencyをループし、紙幣を1枚ずつ取り出し、現在の紙幣の額面合計と可能な組み合わせを計算します.その後、自身を呼び出し、停止条件を満たすか否かを判断する.満たされない場合は、currencyから紙幣を1枚取り出し続け、上記の操作を実行します.停止条件を満たすと、プログラムは前のレベルに戻って実行を続け、resultの値を得ることができます.resultが空でない場合は、この組合せを保存します.サブリストから数を削除します.これはすでに処理されている可能性があります.次にforループを続け、次の組み合わせを試します.
set保存紙幣を使用するので、紙幣の額面は重くありません.つまり、同じ長さの組み合わせに対して、順序を考慮しないと同じ組み合わせになります.同様にsetを使用してユニークな数値を保存します.

#     ，    
def _equal(num:int, sub_list:list):
    #      1
    #          
    if num == value:
        return sub_list       
    
    for elem in currency:
        #     
        total_num = num + elem
        #        
        sub_list.append(elem)
        #      2
        #          
        if num > value:
            return []
        #   
        result = _equal(total_num, sub_list.copy())
        #     
        #        ，     
        if dup:
            length = len(result)
            if length not in unique_set:
                unique_set.add(length)
            else:
                result = []
                
        #         
        #          
        if result:
            total_list.append(result)
        #          
        sub_list.pop()
      
    return []

はい、このセクションの内容はここまでです.完全なコードは微信公衆番号:Python のバックグラウンドで2019511に返信してください.
文章を書くのは容易ではありません.また、サポートを転送してください.