Python 再帰関数関連

質問

再帰関数を解決できなくて困っています、ご教授お願いします！

普通関数で書いたものを再帰関数に変換するのはどう書けばいいですか？
def foo(n, m):
　sum = 0
while m > 0:
sum = sum + n
m = m -1
return sum
これを再帰関数でどう変換します？

回答No.2

cametan_42 · ベストアンサー

ええと、もう一つ書き方お教えしましょう。
多分元の書かれたコード見る限り、多分こっちの方が分かりやすいかな、と思います。
文字通り「再帰関数への変換」です。

ちょっとコメント合わせますが、こう言う思考回路で書いてるんじゃないか、って思います。

def foo(n, m):
　sum = 0　　　　　# 1. アキュムレータ(累積器)を 0 とする
　while m > 0:　　　# 2. m(カウンタ) が 0 以上の場合
　　sum = sum + n　　# a. アキュムレータに n を加算して
　　m = m -1　　　　　# b. カウンタ から 1 を引く
　return sum　　　　# 3. それ以外の時にはアキュムレータを返す

ロジックはこの通りですよね。非常に明解です。

ちなみに、アキュムレータとは、このテの繰り返し計算をする際に、加算等の結果を記憶する変数の事を指します。このコードでは sum がそれに当たりますね。
また、m は繰り返し回数を指定するカウンタです。

実はこのロジック殆どそのままで再帰を書くことが出来ます。
コツは以下の通り。

☆ アキュムレータも関数の引数にしてしまう

これが最大のポイントです。つまり関数の書き始めは

def foo(n, m, sum):

にしてしまうんです。これが最大のコツです。
そうすると、

def foo(n, m, sum):
　m(カウンタ) が 0 以上の場合:
　　アキュムレータに n を加算してカウンタ から 1 を引く
　それ以外の時にはアキュムレータを返す

と言う形が見えてきますね。殆ど元のコードが意図する事と同じです。
もうちょっと言うと

def foo(n, m, sum):
　if m > 0:
　　アキュムレータに n を加算してカウンタ から 1 を引く
　else:
　　return sum

が形として決まるわけですが、平たく言うと、まだ平仮名で残ってる部分が再帰部分になります。
内容は全く元コードと同じなんですが、大元関数のfooを呼び出すところが違ってるわけですね。
んで、再帰のもう一つのポイントは

☆ 元のコードで書いてた部分を引数内の処理にして完結してしまう。

です。コードなんて書かなくて良い、ただ、引数内に計算式をぶちこんじゃえ。こう言うわけです。
つまり、

def foo(n, m, sum):
　if m > 0:
　　return foo(n, m - 1, sum + n)　# 引数内に注目!
　else:
　　return sum

3行目を見てみればわかりますが、元のコードの

・アキュムレータに n を加算する。
・カウンタ から 1 を引く。

って2つの作業を foo の引数内で処理してる事が分かるでしょう。
これで終わり、です。

ちょっと実行してみましょうか。

>>> foo(1, 10, 0)
10

キチンと動きますね。
オリジナルのコードにあった

　sum = 0　　　　　# 1. アキュムレータ(累積器)を 0 とする

ってのが消えて、外部から第3引数として0を与える、って事だけが違いますね。
ただ、一々第3引数に0を与える、分かりきってるのにメンド臭い、って場合は、Pythonではデフォルト引数ってのが使えるんで、コードの第1行目を次のように書き換えれば

def foo(n, m, sum = 0): # ここの第3引数を sum = 0 とする
　if m > 0:
　　return foo(n, m - 1, sum + n)
　else:
　　return sum

第3引数を与えなくても問題無く動きます。

>>> foo(2, 10)
20

なお、この形式の再帰を末尾再帰(tail-call-recurcive)と呼びます。

お礼

とても解りやすかったです。ありがとうございます。
私は再帰定義を複雑に考えていました。

回答No.1

yelser

同じ内容なら

def foo(n,m):
　　if m < 0:
　　　　retern 0
　　else:
　　　　return n + foo(n,m-1)

です。
全角空白2つを半角空白4つでインデントし直してください。

補足

yelser　様

ありがとうございます。
shellでやると次の結果がでます、
>>> def foo(n, m):
... if m < 0:
... return 0
... else:
... return n + foo(n, m-1)
...
>>> foo(2, 10)
22