Pythonの再帰関数の動作の流れについて

pythonでsortメソッドの原理として分割統治法のコードを書く練習をしています。
下記の様な再帰関数が出てくるのですが、どの様に動作しているのか分かりません。
動作を追えるようにprintでdata1,data2を出力しています。

def mergesort(data):
　n = len(data)
　　if n <= 1:
　　return data
　else:
　　data1 = mergesort(data[0:n//2])
　　data2 = mergesort(data[n//2:n])
　　print('data1',data1)
　　print('data2',data2)
　　return data1, data2

data=[5,3,2,8,4,7,10]
print(mergesort(data))

実行結果は下記の様になります。
data1 [3]
data2 [2]
data1 [5]
data2 ([3], [2])
data1 [8]
data2 [4]
data1 [7]
data2 [10]
data1 ([8], [4])
data2 ([7], [10])
data1 ([5], ([3], [2]))
data2 (([8], [4]), ([7], [10]))

ものすごく漠然とした質問で恐縮ですが、何となくは理解できるのですが、厳密に動作の流れを言葉で説明できるように整理したいので、どなたか流れが分かるようにご説明頂けないでしょうか。
宜しくお願い致します。

質問者からの補足コメント

• コードの全体像は下記になります。
  
  import ita
  
  def mergesort(data):
  　n = len(data)
  　　if n <= 1:
  　　return data
  　else:
  　　data1 = mergesort(data[0:n//2])
  　　data2 = mergesort(data[n//2:n])
  　　print('data1',data1)
  　　print('data2',data2)
  　　return data1, data2

    補足日時：2020/02/27 12:23

• def merge(data1,data2):
  　result = ita.array.make1d(len(data1) + len(data2))
  　1 = 0
  　i2 = 0
  　for i in range (len(result)):
  　　if (i2 >= len(data2) or (i1 < len(data1) and data1[i1] <= data2[i2])):
  　　　result[i] = data1[i1]
  　　　i1 = i1 + 1
  　　else:
  　　result[i] = data2[i2]
  　　i2 = i2 + 1
  　return result
  
  data=[5,3,2,8,4,7,10]
  mergesort(data)

    補足日時：2020/02/27 12:24

No.4 回答者： tknakamuri 回答日時： 2020/03/01 10:49

def mergesort の次の行に

print('arg data =', data)
と入れるだけでも随分見通しが良くなるよ。

idle等のデバッガも合わせて使えば何が起きてるか
楽々解るはず。

この回答へのお礼

ありがとうございます。
IDLE使ってみてみたのですが、そもそもこれを使ったことなかったので、デバッグして流れを追って調べる練習しておきます。
初心者にお勧めのデバッグのソフトなどありましたら教えて頂ければと思います。

お礼日時：2020/03/02 16:05

No.3 ベストアンサー 回答者： rinkun 回答日時： 2020/02/28 09:16

再帰関数の動作を見たいということならprint文の入れ方が中途半端です。

下記のように関数の入口と出口の両方で表示させないと実態が見えません。
なお下記例では関数の呼び出し関係を見せるために引数stackを追加しています。
# ソートをする関数になっていないので関数名を変更しています。

def conquer(data,stack=[]):
　print('in depth:',len(stack)+1,' data:',data,' stack:',stack)
　n = len(data)
　if n <=1:
　　print('out depth:',len(stack)+1,' above')
　　return data
　else:
　　data1 = conquer(data[:n//2],stack+[1])
　　data2 = conquer(data[n//2:],stack+[2])
　　ret = (data1,data2)
　　print('out depth:',len(stack)+1,' data:',ret,' stack:',stack)
　　return ret

data=[5,3,2,8,4,7,10]
print(conquer(data))

実行結果:
in depth: 1 data: [5, 3, 2, 8, 4, 7, 10] stack: []
in depth: 2 data: [5, 3, 2] stack: [1]
in depth: 3 data: [5] stack: [1, 1]
out depth: 3 above
in depth: 3 data: [3, 2] stack: [1, 2]
in depth: 4 data: [3] stack: [1, 2, 1]
out depth: 4 above
in depth: 4 data: [2] stack: [1, 2, 2]
out depth: 4 above
out depth: 3 data: ([3], [2]) stack: [1, 2]
out depth: 2 data: ([5], ([3], [2])) stack: [1]
in depth: 2 data: [8, 4, 7, 10] stack: [2]
in depth: 3 data: [8, 4] stack: [2, 1]
in depth: 4 data: [8] stack: [2, 1, 1]
out depth: 4 above
in depth: 4 data: [4] stack: [2, 1, 2]
out depth: 4 above
out depth: 3 data: ([8], [4]) stack: [2, 1]
in depth: 3 data: [7, 10] stack: [2, 2]
in depth: 4 data: [7] stack: [2, 2, 1]
out depth: 4 above
in depth: 4 data: [10] stack: [2, 2, 2]
out depth: 4 above
out depth: 3 data: ([7], [10]) stack: [2, 2]
out depth: 2 data: (([8], [4]), ([7], [10])) stack: [2]
out depth: 1 data: (([5], ([3], [2])), (([8], [4]), ([7], [10]))) stack: []
(([5], ([3], [2])), (([8], [4]), ([7], [10])))

この回答へのお礼

いつもありがとうございます。
なるほど、前後で結果を出力すると流れがとてもきれいに追えました。
時分で書けるようにならないと完全に理解したとは言えないと思いますが、とてもしっくりきました。
再帰関数を書く練習として良い例題などご存じでしたら教えて頂ければと思います。フィボナッチ数列しかやったことありません。

お礼日時：2020/03/02 16:18

No.2 回答者： siffon9 回答日時： 2020/02/28 05:39

「おおざっぱに見る」というNo.1の方の考えに賛成です。

流れを理解するにはWikipediaのマージソートの説明とアニメーションがわかり易くないでしょうか？
https://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%BC …



mergeは、２つの配列の先頭要素を比べて、小さい方の先頭要素をとりだして、新しい配列に加えていくという処理をしなければいけません。

def merge(d1, d2):
　#二つの配列のマージ結果をいれる配列
　d = []
　#二つの要素の先頭要素を指すインデックス
　i1 = 0
　i2 = 0

　#二つの配列の先頭要素(i1,i2の指す要素)のうち小さい方をdに追加する処理を
　#どちらかの配列要素がなくなるまで繰り返す
　while (i1 < len(d1)) and (i2 < len(d2)):
　　if d1[i1] < d2[i2]:
　　　d.append(d1[i1])
　　　i1 += 1
　　else:
　　　d.append(d2[i2])
　　　i2 += 1

　#二つの配列のどちらかで余った要素をdに追加する
　if(i1 < len(d1)):
　　d += d1[i1:]
　if(i2 < len(d2)):
　　d += d2[i2:]
　#配列dを返す
　return d


def mergesort(data):
　n = len(data)
　if n <= 1:
　　return data
　else:
　　data1 = mergesort(data[0:n//2])
　　data2 = mergesort(data[n//2:n])
　　return merge(data1, data2)


data=[5,3,2,8,4,7,10]
print( mergesort(data) )

この回答へのお礼

mergesortの原理、教えて頂いたリンクのアニメーションで良く分かりました。再起については理解ほどほどで、数をこなして感覚つかむようにします。ありがとうございました。

お礼日時：2020/03/02 16:07

No.1 回答者： kmee 回答日時： 2020/02/27 23:22

再帰関数を理解するためには、むしろ「おおざっぱに見る」ことの方がいいのではないか、と思っています。

過去に何度か「再帰関数がわからない」とかいう質問を見ましたが。
詳細な動きを追い掛けようとして、呼ばれたり戻ったりしているうちに混乱してしまった、というのが多いように感じました。



マージソートのアルゴリズムは次の通りです。

(1)配列の半分をソートする。
(2)残りをソートする。
(3) (1)と(2)を結合(マージ)する。
　すでにソート済みなので、先頭から順番に処理していくだけでよい。そのため負荷が少ない

このときの(1),(2)のソートは、実際にはどのアルゴリズムでも問題ありません。
今はマージソートのプログラムを作っているのだから、そのままマージソートを使いましょう、というのが、一般的なマージソートのプログラムです。

(1)配列の半分をマージソートする。
(2)残りをマージソートする。
(3) (1)と(2)を結合(マージ)する。

この(1)(2)で、今のプログラムを又呼び出すので「再帰呼び出し」になります。
名前が同じ、実行する行番号が同じ、ということで混乱しそうになるだけです。



なお、そのプログラムは「マージソート」になっていません。
というかソートにもなっていません。
肝心の「マージ」が間違えています。

この回答へのお礼

ありがとうございます。大雑把に理解して、あとは量をこなして慣れていくように練習しようと思います。何かお勧めの練習問題とかありましたら教えて頂ければと思います。

お礼日時：2020/03/02 16:08