この再帰関数は何回繰り返されますか？

Question

私は、次のように、再帰関数を持ってここで、b> = 0

def multiply(a,b): 
    if b == 0: 
     return 0 
    elif b % 2 == 0: 
     return multiply(2*a, b/2) 
    else: 
     return a + multiply(a, b-1) 

私は関数はという点aとbで を実行する回数を知っていただきたいと思い

。おかげさまで

Answer 1

私はここで間違っているかもしれませんが、あなたの機能は意図した通りに機能しないと思います。再帰では、プロペラの終了基準として最も重要なことは、それが永遠にelsewaysで実行されるためです。

終了基準はa==0ですが、各再帰呼び出しでは、aを減らしません。単に&という紙のシミュレーションをa = 5で行い、それがいつでも停止するかどうかを確認してください。

Answer 2

bのバイナリ表現（Bと呼ぶ）が1で終わる場合、xxxx1のように乗算の次の呼び出しはB = xxxx0です。

Bが0で終わる場合、Bの次の値よりもxxxx0の方がxxxxです。

これでbのバイナリ表現の数字は、0の場合は1つのコールを追加し、1の場合は2つのコールを追加します。合計コール数がlength of initial B + number of ones in initial Bに等しいことを合計します。