【Python】再起関数を無理やり理解してみた

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

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

# 記事のターゲット層

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

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

```python: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行表示しているだけです

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

```python: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)
```

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

基本的な**再起関数の書き方**は、
1. 再起関数が自動的に回ってくれる**きっかけ**を作る
2. 再起関数内に、**終了条件（if文）** を入れる
3. 変数を**自分が**カウントアップする
4. 再起関数内で**必ず**自分を呼び出す

ことだと思っています。

どれがどれに該当するかというとこんな感じ
```python: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万回のループをしている時も再起が終わるまでずっと保持されています。

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

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

---

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

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

```python: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)
```

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

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

# 無理やり理解してみる

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


さっきまでのこのコードが、
```python:recursive.py
def recursiveFunc(data, index, end):
	if index == end:
		return
    # こいつを展開するよ
   	recursiveFunc(data, index + 1, end)
	print(data[index])
```
こんな感じに

```python: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を変えながら出力することができます。

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

```python: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には、この再起が意図せず無限ループにならないように、**強制的に切り上げる**よう実装されているようです。
```python:loop.py
def hello():
	hello()

while True:
	hello()
```

```python: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」パッケージ** をいじれば変えられるっぽいけど、**スタックオーバーフロー**に気をつける必要があります。

https://docs.python.org/3/library/sys.html#sys.setrecursionlimit

自分の環境では、スタック領域は`8192KB(8MB)`しか確保されていません。
`ulimit`コマンドで確認ができます
```bash:Terminal
ulimit -s
>>> 8192
```
 > `ulimit` ... 使用できるリソースを制限する
 -s ...スタック領域のサイズのみ出力
※-a ...全て表示

# 参考にしたサイト

https://stackoverflow.com/questions/3323001/what-is-the-maximum-recursion-depth-in-python-and-how-to-increase-it