この再帰文はどのように機能しますか？

Question

私は同じことをする2つの再帰的なステートメントを持っています。最初のステートメントの仕組みを理解していますが、2番目のケースでは混乱します。

1）

def recurPower(base, exp): 
''' 
base: int or float. 
exp: int >= 0 

returns: int or float, base^exp 
''' 
# Base case is when exp = 0 
if exp <= 0: 
    return 1 

# Otherwise, exp must be > 0, so return 
# base* base^(exp-1). This is the recursive case. 
return base * recurPower(base, exp - 1) 

それは依然として変数「ベース」を残す自体をリコールしているが、この最初の場合は後ろ方法周りたびに乗算します。この場合

2）

def recurPowerNew(base, exp): 
''' 
base: int or float. 
exp: int >= 0 

returns: int or float; base^exp 
''' 
# Base case is when exp = 0 
if exp <= 0: 
    return 1 

# Recursive case 1: exp > 0 and even 
elif exp % 2 == 0: 
    return recurPowerNew(base*base, exp/2) 

# Otherwise, exp must be > 0 and odd, so use the second 
# recursive case. 
return base * recurPowerNew(base, exp - 1) 

私はそれはそれは、でも数であればとき、作用している最初のケースのように何の変数は、ありませんどのように機能するかを理解していません数はそれだけでは常に異なるパラメータを与えているようですが、実際には "ベース"のような特定の変数に対処しません。

メソッドにボディがない場合、パラメータは値を返しますか？

Answer 1

最初のパラメータは値を返さず、関数は戻ります。

第2に、再帰的な問題と混同している可能性のある箇所がわかります。再帰では、変数に "acted"が必要ではありません。再帰が最終的にベースケースに達する限り、値は返されます。

たとえば、整数に1を返す無駄な再帰関数があります。最終的には整数から1を減算することにより、我々はn個のベースケースに到達しますので、任意の整数nに1を返します

def foo(n): 
    if n <= 1: 
    return 1 
    else: 
    return foo(n-1) 

fooが再帰的な問題に< 1.

キーは、ベースを考えることですそれぞれの反復でベースケースに近づいていることを確認してください。

いずれの再帰関数でも、ベースケースはゼロの指数です。 2番目の再帰式は、nが偶数の場合はいつでもベースケースへのショートカットをとっています。すべての均等な力に対して、x^n =（x^2）^（n/2）

の例を使って作業することで、基底の2乗を単純に計算して半分にすることができます。偶数EXP = 10が、第1の戻り値はなり

recurPowerNew(2, 10) 

ためで見つめる

：

recurPowerNew(2 * 2, 5) 

この事実を利用してしている2^10 =（2^2）^ 5。今度は、新しいリターン関数を評価する必要があります。新しい関数を生成したにもかかわらず、exp = 0の基本ケースに向かって進んでいます。だから、最終的に答えが得られると期待しています。

今、私たちが、戻り値があることを行っている奇妙な基盤を持っている：

4 * recurPowerNew(4, 4) 

は、今、私たちは再び我々が評価しなければならない機能を持っているが、それはそれだけで新しい関数を返し、そうであっても です。

4 * recurPowerNew(4 * 4, 2) 

。

4 * recurPowerNew(16 * 16, 1) 

もう1つの要因があります。

4 * (256 * recurPowerNew(256, 0)) 

ああ、私たちは基本ケースにあり、これ以上の再帰はありません。

4 * 256 * 1 

、我々は結果を評価し、この作品を作る鍵は、すべての繰り返しで、我々はベースケースに近くなった、と我々は非常に少ないそれを行うことができたということです

1024 

を得ることができます呼び出しが2で割ると指数が1を減算するよりも速く減るためです。

Answer 2

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

print recurPowerNew(3, 4) 

のでbaseは3であるとexpこれはあなたが関係している場合に該当し、かつ呼び出します8です。

return recurPower(9, 2) 

...どの同じ場合に該当します。

return recurPower(81, 1) 

ah-ha！これは奇妙なケースです。したがって、これは、

return 81 * recurPower(81, 0) 

のようになります。したがって、乗算の第2項は1であるため、スタック全体を81まで戻します。これを実行すると、2の累乗ではない数値にも適用されます。

この点は、と非常に多く、が最初の方法より効率的です。それは、指数のビットごとに1つまたは2つのスタックフレームを生成する。最初の方法はexponentのスタックフレームを生成します！ （

 return base * recurPowerNew(base*base, exp // 2) 

：

なお、第二の例では、さらに効率的指数が奇数である場合にそれを観察することにより行うことができる、いずれかを減算しても指数をもたらすので、我々はちょうどそれを直接扱うことができPython 2を使用している場合は//の代わりに/を使用してください。