Python再帰関数を理解しようとしています

Question

"？"の場所で0と1を変更して2進数を美しく生成する次のスニペットがあります。しかし、私はこのコードがどのように機能するのか分かりません。特に、行str_list [idx] = "？"。なぜですか？ " idxの位置に復元が開始されます。

再帰を書く際にこれについてどのように考えるべきでしょうか？ここで

は、このような再帰関数を作成する方法上の任意のアドバイスは良くなってきて私を助けるコード

def gen_bin(str_list): 
    if "?" not in str_list: 
     print "".join(str_list) 
     return 

    idx = str_list.index("?") 
    gen_bin(str_list[:idx] + ["0"] + str_list[idx+1:]) 
    gen_bin(str_list[:idx] + ["1"] + str_list[idx+1:]) 

    str_list[idx] = "?" 


gen_bin(list("1??")) 

です。

お時間をありがとう、

Answer 1

2はありません再帰的定義への部分：

1. 終了条件。この部分は重要であり、頻繁に最初に現れます。終了条件は、あなたが "完了"しているかどうかを知るためにテストするものです。

   一般に、再帰関数には、ある種の「自然な」終了条件があります。たとえば、フィボナッチシーケンスは、1に戻るときに終了します。ファクタルは、1に戻るときに終了します。リスト処理は、空のリストを取得すると終了します。文字列処理は空の文字列で終了します。

   どんなものでも、終了条件が正しく定義され、正常にチェックされていない限り、再帰関数は失敗します - 一般的にはスタックオーバーフローが発生するまで無限ループまたは再帰を行います。

   このため、ほとんどの再帰関数は次のようになります。

   def recursive_func(arg): 
       if terminating_condition(arg): 
        return simplest_value 
   
       # more code here 
       recursive_func(reduced_form(arg)) 
   

2. 再帰的な関係。終了条件のテストを確認したら、再帰的な関係を呼び出さなければなりません。一般に、これは、同じ再帰関数のわずかに小さい形式を含む計算を実行することを意味します。

   例：

   のn！ ：= n *（n-1）！

   FIB（N）= FIB（N-1）+ FIB（N-2）

   LEN（ヘッド：尾）：= 1 + LEN（尾）

実世界の例

のはあなたの例を見てみましょう：

def gen_bin(str_list): 
    if "?" not in str_list: 
     print "".join(str_list) 
     return 

    idx = str_list.index("?") 
    gen_bin(str_list[:idx] + ["0"] + str_list[idx+1:]) 
    gen_bin(str_list[:idx] + ["1"] + str_list[idx+1:]) 

    str_list[idx] = "?" 

gen_bin(list("1??")) 

この関数は古典的な構造に従っていることは明らかです。最初の段落は、終了条件のテストです。この場合、終了条件は '？'がないことです。置換する文字列に挿入します。

関数の残りの部分は、再帰関係専用です。この場合、これは、最初に現れた '？' '0'または '1'のいずれかの文字列で再帰します。

私はこれがあまり良いコードではないと主張します。まず第一に、最後の割り当て、str_list[idx] = "?"は何もしません。私はこのコードが最近修正されたと思われる。スライスを使用する代わりにstr_list[idx]に '0'と '1'を直接設定して、おそらくstr_listを編集しました。

しかし、これは良いコードではありません。なぜなら、結果がすべて印刷されるからです。バイナリ文字列を出力しようとするのではなく、バイナリ文字列のリストを返した方が良いでしょう。

Answer 2

が機能gen_bin()は、単にこのラインで、入力引数リスト内?の最初の出現を探します。

idx = str_list.index("?") 

そしてちょうど、その場所に0を挿入その新しいリストを新しい引数として再帰的に実行します。

gen_bin(str_list[:idx] + ["0"] + str_list[idx+1:]) 

次に、1あって、再び再帰的に実行します：

gen_bin(str_list[:idx] + ["1"] + str_list[idx+1:]) 

何?がstr_listに存在しない場合、それは単に引数を出力します。

ライン：

str_list[idx] = "?" 

が不要であり、あなたは、次のコードを実行している観察することができ、完全に何も、ない：

def gen_bin(str_list): 
    if "?" not in str_list: 
     #print "".join(str_list) 
     return 

    idx = str_list.index("?") 
    gen_bin(str_list[:idx] + ["0"] + str_list[idx+1:]) 
    gen_bin(str_list[:idx] + ["1"] + str_list[idx+1:]) 

    print str_list 
    str_list[idx] = "?" 
    print str_list 

gen_bin(list("1??")) 

返します

['1', '0', '?'] 
['1', '0', '?'] 
['1', '1', '?'] 
['1', '1', '?'] 
['1', '?', '?'] 
['1', '?', '?']