2016-05-04 18 views
2

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

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

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

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??")) 

です。

お時間をありがとう、

答えて

3

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を編集しました。

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

+0

詳細な説明をありがとうございます。コードの行が何もしていないことがわかります。このコードは、2回の再帰呼び出しを行います。 1つは0、もう1つは1です。1行または1つの呼び出しで両方のサブ再帰関数を呼び出すために同じ関数を変更するにはどうすればよいですか。 – user1335161

+0

それはあなたがしようとしていることに依存します。おそらく最も簡単な方法は2つを列挙することです: 'call( '0')、call( '1')' –

3

が機能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', '?', '?'] 
+0

私に説明してくれてありがとう。あなたが正しいです。そのコード行は何もしていません。今私は、2つの再帰呼び出し(1つは0を挿入し、もう1つは1を挿入)を組み合わせて、関数内で単一の再帰呼び出しにする方法はありますか? – user1335161

+0

私は理解できません、なぜこれらの2つの通話を組み合わせたいのですか? –

関連する問題