経緯

ソートアルゴリズムの「クイックソート」や「マージソート」。
これらは再起関数で説明されていることが多く、その 「再起している部分」 の仕組みを解説している記事が少なかった。

他言語で再起関数を実装したことがある人だとスムーズに読めるかもしれませんが、近年pythonからプログラミングを始める人が多いので、仕組みを解説する記事があってもいいのかなと

記事のターゲット層

再起関数は知ってるけど自分で実装するとなると手が止まる人
他人のコードで再起を見たときに、なんとなくわかった気になるだけの人
コードを追ってると、どの変数にどの値が入っているのかごちゃごちゃになる人
　
向けに、pythonで解説してみようと思います。
あくまで、いろんなサイトを見てきて自分流になってる部分があるのであしからず。

よくある例

始めに以下のようなfor文を考えてみます。

for_loop.py

data = ["h", "e", "l", "l", "o"]
length = len(data)

for i in range(length):
	print(data[i])

data変数にはh, e, l, l, oの文字が1つずつ要素に格納されており、for文で1行1行表示しているだけです

このソースコードを 「再起」 で書き換えると以下のように書けます

recursive.py

def recursiveFunc(data, index, end):
	if index == end:
		return
	print(data[index])
	recursiveFunc(data, index + 1, end)

data = ["h", "e", "l", "l", "o"]
start = 0
end = len(data)
recursiveFunc(data, start, end)

こちらも実行してみて、同じような結果になったでしょうか。

基本的な再起関数の書き方は、

再起関数が自動的に回ってくれるきっかけを作る
再起関数内に、終了条件（if文） を入れる
変数を自分がカウントアップする
再起関数内で必ず自分を呼び出す

ことだと思っています。

どれがどれに該当するかというとこんな感じ

recursive.py

def recursiveFunc(data, index, end):
	# 2. 表示したい「index」が、最後の「end」まで来たら終わり
	if index == end:
		return
	# 該当の要素を出力
	print(data[index])
	# 3,4. 「index」をカウントアップして、再起（自分自身を呼び出し）する
	recursiveFunc(data, index + 1, end)

data = ["h", "e", "l", "l", "o"]
# indexを何番目から始めるか
start = 0
# どこまでループさせるか
end = len(data)
# 1. 再起関数を自動的にループさせるためのきっかけ
recursiveFunc(data, start, end)

なので、for文と再起関数の関係を表にまとめると、

	for文	再起関数
きっかけ	`for i in range(5)`	recursive(data, i, ...)
いつ終わる	5に来たら	自分でif文を記述
カウントアップ	自動的にiへ加算	自分で`i+=1`を記述

かな？
こうみると全部for文でいいじゃんってなるけど、アルゴリズムを学んでいると再起で書いたほうが絶対いいやつとかがあるので、しぶしぶ勉強しましょう。

注意点

2. 再起関数内に、終了条件（if文）を入れる
は再起関数の先頭に書くことが多いです。

理由は、終了条件より先に再起関数の処理が走ると、単純に無限ループになってしまうからです。

また、再起関数内に変数を定義しない方がいいです。
結局、関数を使って（呼び出して）ループをしているため、1回目2回目で呼び出された関数の変数は、別々のメモリとして保存されているため、1万回2万回のループをしている時も再起が終わるまでずっと保持されています。

つまり、同じ内容の変数が量産されてメモリを圧迫するので、関数の引数に渡してあげるほうが親切です。

※最後にある「補足」でちょい解説

（本題）出力結果を予測してみよう

ここからが本題です。
以下のコードで何が出力されるか（あるいはされないか）当ててみてください。
（当たった人はもう記事を読む必要ないかも。。）

recursive.py

 # 再起関数
def recursiveFunc(index, end):
	if index == end:
		return
    # さっきのprint関数と再起関数を入れ替えただけ
	recursiveFunc(index + 1, end)
	print(data[index])

data = ["h", "e", "l", "l", "o"]
start = 0
end = len(data)
recursiveFunc(start, end)

何も出力されずにreturnされる
逆からo, l, l, e, hが出力される
さっきと同様にh, e, l, l, oが出力される
hが5回出力されちゃう
無限ループで終わらなくなる
そもそも実行できない

いろんなパターンが予想されますね

無理やり理解してみる

自分がコードレビューなどで説明するやり方で解説します。
しつこいようですが、再起関数というのは関数を呼び出しているんです。
つまり、呼び出したコードに、関数を展開すればいいわけです。
わかりやすいように、変数の中身もコメントアウトで表示しています。

さっきまでのこのコードが、

recursive.py

def recursiveFunc(data, index, end):
	if index == end:
		return
    # こいつを展開するよ
   	recursiveFunc(data, index + 1, end)
	print(data[index])

こんな感じに

recursive.py

# data, index == 0, end == 5
def recursiveFunc(data, index, end):
	if index == end:
		return
        ###----- 展開はじめ -----###
	recursiveFunc(data, index + 1, end){
		# data, index == 1, end == 5
		if index == end:
			return
		recursiveFunc(data, index + 1, end)
		print(data[index])
     }###----- 展開終わり -----###
	print(data[index])

{}を使って、中身を展開してみました。
こうやってみると、どこの時点で変数の値がどうなっているのかが追いやすくなると思います。
それぞれの関数は、変数名は同じでも値は異なるので
data[0], data[1]のようにindexを変えながら出力することができます。

大きくなっちゃいますが、全て書いてみます。

recursive.py

# data, index == 0, end == 5
def recursiveFunc(data, index, end):
	if index == end:
		return
	recursiveFunc(data, index + 1, end){
		# data, index == 1, end == 5
		if index == end:
			return
		recursiveFunc(data, index + 1, end){
			# data, index == 2, end == 5
			if index == end:
				return
			recursiveFunc(data, index + 1, end){
				# data, index == 3, end == 5
				if index == end:
					return
				recursiveFunc(data, index + 1, end){
					# data, index == 4, end == 5
					if index == end:
						return
					recursiveFunc(data, index + 1, end){
						# data, inex == 5, end == 5
						# ここで再起終了、{}で囲まれた関数が終了する
						if index == end:
							return
						# 実行されない
						recursiveFunc(data, index + 1, end)
						# 実行されない
						print(data[index])
					}
					# data[4] == "o"
					print(data[index])
				}
				# data[3] == "l"
				print(data[index])
			}
			# data[2] == "l"
			print(data[index])
		}
		# data[1] == "e"
		print(data[index])
	}
	# data[0] == "h"
	print(data[index])

全て展開がし終わったので、あとは上から順に実行されていくだけです。
よって、index == 5になる時点の関数でreturnされてから
o, l, l, e, hと出力されていく様子がわかりますね。

従って解答は
2. 逆からo, l, l, e, hが出力される
でした。

環境

System	Version
OS	MacOS Monterey(12.1)
bash	GNU bash, version 3.2.57(1)-release
python	3.8.8
stack size(Kbytes)	8192

※stack sizeについて補足でちょい解説

終わりに

いまだにこの方法で再起関数を理解することが多いです。
パッとみた瞬間に理解できるようになりたい＆自由に記述できるようになりたいですね

自分が始めたての時も全くイメージがつかず苦戦した記憶があるので誰かの助けになってると嬉しいです。

補足

pythonには、この再起が意図せず無限ループにならないように、強制的に切り上げるよう実装されているようです。

loop.py

def hello():
	hello()

while True:
	hello()

Terminal

Traceback (most recent call last):
  File "loop.py", line 5, in <module>
    hello()
  File "loop.py", line 2, in hello
    hello()
  File "loop.py", line 2, in hello
    hello()
  File "loop.py", line 2, in hello
    hello()
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

再起の深さは、「1000回まで」 と決められているみたい。
確かに、普通に書いてたら1000回超えることなんてないし、自分の終了条件が間違っている可能性の方が高いかも。

その1000回も 「sys」パッケージ をいじれば変えられるっぽいけど、スタックオーバーフローに気をつける必要があります。

自分の環境では、スタック領域は8192KB(8MB)しか確保されていません。
ulimitコマンドで確認ができます

Terminal

ulimit -s
>>> 8192

ulimit ... 使用できるリソースを制限する
-s ...スタック領域のサイズのみ出力
※-a ...全て表示

参考にしたサイト