ＰｙｔｈｏｎＶｅｒ３の再帰について

質問

現在、再帰について勉強しています。
関数のステートメントブロックの中に同じ関数を２か所使った場合の、処理される順番がよく解りません。
そこで、プログラムが表示されている状態で、Ｅｎｔｅｒキーを押す毎に１行ずつ処理が進んで行き、今どの行が働いたかが分る様なソフト又は方法がないでしょうか。
よろしくお願いいたします。

回答No.4

kmee · ベストアンサー

実行順序は、あくまで、次の通りです。
02)
03)→ifを満していたら、04)のreturnで終了
05)
06)
07)
08)
09)
10)で関数の最後に来たので(自動的にreturnで)終了

再帰の先まで含めた動作順序を考えるときも、他の関数と考え方は一緒です。
・returnしたら、呼び出したところへ戻ってきます。
・ローカル変数は、現在実行中の関数の中だけで有効です。
#2で述べたように、別の関数だと思うくらいがいいです。

02) ここのlengを leng_0とする
03)→ifを満していたら、04)のreturnで終了
05)
06)→br(leng-1)の呼び出し
　　1-02) ここでのlengをleng_1 とする。 leng_1とleng_0とは別の変数になる
　　1-03)→ifを満していたら、1-04)のreturnで終了
　　1-05)
　　1-06)→br(leng-1)の呼び出し
　　　　1-1-02) ここでのlengをleng_1_1 とする。 leng_1_1とleng_1とleng_0とは別の変数になる
　　　　1-1-03)→ifを満していたら、1-1-04)のreturnで終了
　　　　1-1-05)
　　　　1-1-06)→br(leng-1)の呼び出し
　　　　　　...
　　　　←戻ってくる
　　　　1-1-07)
　　　　1-1-08)→br(leng-1)の呼び出し
　　　　　　...
　　　　←戻ってくる
　　　　1-1-09) ここでのlengはleng_1_1
　　　　1-1-10)で関数の最後に来たので(自動的にreturnで)終了
　　←戻ってくる
　　1-07)
　　1-08)→br(leng-1)の呼び出し
　　　　...
　　←戻ってくる
　　1-09) ここでのlengはleng_1
　　1-10)で関数の最後に来たので(自動的にreturnで)終了
←戻ってくる
07)
08)→br(leng-1)の呼び出し
　　2-02) ここでのlengをleng_2 とする。leng_2は、 leng_1ともleng_0とも別の変数になる
　　2-03)→ifを満していたら、2-04)のreturnで終了
　　2-05)
　　2-06)→br(leng-1)の呼び出し
　　　　...
　　←戻ってくる
　　2-07)
　　2-08)→br(leng-1)の呼び出し
　　　　...
　　←戻ってくる
　　2-09) ここでのlengはleng_2
　　2-10)で関数の最後に来たので(自動的にreturnで)終了
←戻ってくる
09) ここでのlengはleng_0
10)で関数の最後に来たので(自動的にreturnで)終了

> ０６）でｌｅｎｇ－１が４になって

ということは、leng=5ですね(※1)

> ０２）に飛び

ステップ実行では同じ02)に飛んだように見えますが、実際には 1-02)に該当するものに飛んでいます。

> ０４）のｒｅｔｕｒｎで

これも、04)ではなく 1-04)です

> ０７）に飛び「ｂ」をｐｒｉｎｔして

returnとあるように、「飛んで」きたのではなく「戻って」きます。さらに言えば、06)の後に戻ります。
「飛ぶ」だと、どこへでも行けるような感じですが、「戻る」だと「呼んだところへ戻る」というニュアンスがあって、動作を的確に表現していると思います。

> ０８）の関数２において、ｌｅｎｇが「６」になり

(※1)にあるように、leng=5です。この関数中で、lengが変更されるものはありません。
なので、「lengが6になる」ことはありません。
「lengが5になる」こともありません
「lengは最初から5のまま」です。

同じ行を実行しているのに、違う関数になっている、という点が再帰の理解しづらい点ではないか、と思います。

お礼

Ｋｍｅｅさま
大変申し訳ありませんが、私のスキルではどうしても理解できません。
Ｐｙｔｈｏｎの参考書を最初から読み直してみます。
しばらくしてから、又今回と関連した質問をすると思いますので、その時にもう一度回答お願いいたします。

回答No.3

kmee

「5」でないなら、何が来ると思いますか?
なぜそう考えたのか、と、実際の動作の違いを知るのが、理解への近道な気がします。

その表示は、それぞれ、次のように実行されたでのものです。

a※ 元の関数 br(7)の 05)
　※ 元の関数 br(7)→関数1 br(7-1)の実行
a　　※ 元の関数 br(7)→関数1 br(7-1)の 05)
　　　※ 元の関数 br(7)→関数1 br(7-1)→関数1 br(6-1)の実行
a　　　　※ 元の関数 br(7)→関数1 br(7-1)→関数1 br(6-1)の 05)
　　　　　※ 元の関数 br(7)→関数1 br(7-1)→関数1 br(6-1)→関数1 br(5-1) → leng=5-1=4なので 04)でreturn
b　　　　※ 元の関数 br(7)→関数1 br(7-1)→関数1 br(6-1)の 07)
　　　　　※ 元の関数 br(7)→関数1 br(7-1)→関数1 br(6-1)→関数2 br(5-1) → leng=5-1=4なので 04)でreturn
5　　　　※ 元の関数 br(7)→関数1 br(7-1)→関数1 br(6-1)の 09), leng = 6-1=5
c　　　　※ 元の関数 br(7)→関数1 br(7-1)→関数1 br(6-1)の 10)
　　　※ 元の関数 br(7)→関数1 br(7-1)→関数1 br(6-1) の終了
b　　※ 元の関数 br(7)→関数1 br(7-1)の 07), leng=6

補足

何度もありがとうございます。
”５”の後には何が来るかですが

０６）でｌｅｎｇ－１が４になって
０２）に飛び
０３）でｉｆが働いて
０４）のｒｅｔｕｒｎで
０７）に飛び「ｂ」をｐｒｉｎｔして
０８）の関数２において、ｌｅｎｇが「６」になり
０２）に飛んで

と解釈して、後は解からなくなりました。

処理の順番を０１）、０２）を使って、表示出来ないでしょうか。
なにせ初心者ですので、何か基本的な知識が欠けているのかも知れず、非常に恐縮しています。
急ぎませんので、すぐに返事をいただかなくても結構です。
よろしくお願いいたします。

回答No.2

kmee

再帰していないところを省略して。

def br(leng):　　　　　　　＃元の関数
　　if leng < 10:
　　　　return
　　br_1(leng/2)　　　　　　＃関数　１番
　　br_2(leng/2)　　　　　　＃関数　２番

def br_1(leng):　　　　　　　＃関数1
　　if leng < 10:
　　　　return
　　br_1_1(leng/2)　　　　　　＃関数1-１番
　　br_1_2(leng/2)　　　　　　＃関数1-２番
(以下同様に、沢山のbr_*_*..)

このプログラムなら、どういう順番で動作するか、わかりますね?
再帰呼び出しは、上記のような「同じ内容の関数が沢山あって、それを順番に呼び出す」ようなものです。
こう考えれば、疑問が解けるのではないでしょうか。

> １）関数１番、２番の（ｌｅｎｇ／２）は最初はそれぞれ（２００／２）が代入されるんでしょうか。それとも関数２番には最初から（１２．５／２）が代入されるんでしょうか。

br_2(leng/2)がどうなるか考えれば、わかると思います。
brのlengとbr_1のlengは別なものなので、br_1のlengが変化しても、brには影響ありません。

# グローバル変数とか、def ts(a): a.set(1) 等と、呼び出し元のオブジェクトを変更するような仕組みを使っていれば、呼び出し元でも変化します。
# が、これは再帰とは関係の無いことです。

あと、br(200)と整数型で呼び出していますので、lengには常に整数型が入ります。(整数型/整数型は整数型になります)
「関数２番には最初から（１２．５／２）」という状態になっていたとしても、12.5にはなりません。

> ２）「関数２番」から「元の関数」に行き、ｒｅｔｕｒｎが働いた場合、「関数１番」の次の行に行くんでしょうか。それとも「関数２番」の次の行に行くんでしょうか。

「関数2番」から行くのは「関数2番から呼び出された(別の)『元の関数』」であって、「(現在実行中の)元の関数」ではありません。
上記の例で言えば、 brからbr_2を呼び出し、br_2でreturnで戻ったら、brのどこに戻るか、ということです。

ステップ実行だと、同じ関数の中で行ったり来たりしているように見えて、かえって混乱するかもしれません。

「現在実行中の元の関数」の関数1
↓
「「現在実行中の元の関数」の関数1として呼び出された『元の関数』」の関数1
　↓
「「「現在実行中の元の関数」の関数1として呼び出された『元の関数』」の関数1」として呼び出された『元の関数』
　　↓
...
　↓
「「現在実行中の元の関数」の関数1として呼び出された『元の関数』」の関数2
↓
「現在実行中の元の関数」の関数1の次の行
....
となるので、実行箇所だけ見ていたら
関数2でreturn→関数1の次の行
と実行しているように見えてしまうかもしれません。

補足

kmeeさま
何度も回答ありがとうございます。
せっかくですが、よく理解できません。
自分の解らない所が質問しやすい様にプログラムを作りましたので、これで説明させていただきます。

０１）from turtle import*
０２）def br(leng):　　　　　　＃元の関数
０３）　　if leng<5:
０４）　　　　return
０５）　　print("a")
０６）　　br(leng-1)　　　　　＃関数１
０７）　　print("b")
０８）　　br(leng-1)　　　　　＃関数２
０９）　　print(leng)
１０）　　print("c")

１１）br(7)
１２）print("d")
１３）input()

これを実行しますと
a
a
a
b
5
c
b
*
*
*
と表示されます。
ａ
ａ
ａ
ｂ
までは理解出来るんですが、次がどうして５なのかが解りません。
この部分が理解出来たら、全て解るんではないかと期待しています。
解説お願いいたします。

回答No.1

kmee

http://docs.python.jp/3.3/library/pdb.html
とか。

こんなプログラムのことでしょうか?
1:def func(a):
2:　if 終了条件 : return
3:　func(b) #ここと、
4:　func(c) #ここで再帰呼び出し

再帰呼び出しは、呼んだ先の順番まで考えようとすると、ややこしくなります。
呼んだ先での動作は考えず、現在の動作だけを考えます。これだと、実行順序は
1→2(終了条件を満していたら、ここで終了)→3→4
になりますよね?func関数内の実行順序は以上です。

例えば print("X") としたときに、printの中の実行順序まで考えてますか?

お礼

kmeeさま
整理した質問をもう一度質問させていただきます。
本「みんなのＰｙｔｈｏｎ」のなかの例題です。
from turtle import *
def br(leng):　　　　　　　＃元の関数
　"""長さを引数として受取って枝を描く """
　　if leng < 10:
　　　　return
　　forward(leng)
　　left(30)
　　br(leng/2)　　　　　　＃関数　１番
　　right(60)
　　br(leng/2)　　　　　　＃関数　２番
　　left(30)
　　forward(-leng)
br(200)
input()

このプログラムの動きを１行ずつ確認したんですが、どうしても理解出来なかったので、何か良い確認方法がないか、質問いたしました。
あらためて質問させていただきます。
１）関数１番、２番の（ｌｅｎｇ／２）は最初はそれぞれ（２００／２）が代入されるんでしょうか。それとも関数２番には最初から（１２．５／２）が代入されるんでしょうか。

２）「関数２番」から「元の関数」に行き、ｒｅｔｕｒｎが働いた場合、「関数１番」の次の行に行くんでしょうか。それとも「関数２番」の次の行に行くんでしょうか。
表現がややこしいかも分かりませんが、よろしくお願いいたします。

補足

ｋｍｅｅさま
回答ありがとうございます。
とりあえず、お礼だけを言って回答の内容を整理してからもう一度質問させていただきます。