再帰関数

Chatpter.1 - 作った関数はテンプレート

作った関数はテンプレート

「再帰関数さいきかんすう」と読みます。

こんな関数を作ったとします。

def kansuu(x):
    print(x)
    return

kansuu(0)

0

単純に 0 を引数にして関数内で 0 を出力して終了するプログラムです。

これがどのような流れで動いているのかを追ってみます。

↓ 関数が引数を受け取る

def kansuu(0):  # ← ココ
    print(x)
    return

kansuu(0)

↓ 0 を出力する

def kansuu(0):
    print(0)  # ← ココ
    return

kansuu(0)

0

↓

def kansuu(0):
    print(0)
    return  # None を返す

kansuu(0)

↓

def kansuu(0):
    print(0)
    return

None  # 関数が戻り値に化ける

ここで None に化けても無意味なので、プログラムはこのまま終了します。

さて、この kansuu(0) で呼び出す関数は、どの関数を使って処理しているのでしょうか？
当然、先に書かれている def kansuu(x): を使って処理されています。

と思ったら大間違い！

関数が呼び出されたら、def kansuu(x): の関数全体をそっくりコピーし、コピーした関数を使って処理されます。
コピー機でコピーしたら、コピーしたほうに書き込むのと同じ要領です。
作った関数は見本です。テンプレートです。
コピーした関数が実際にどこかに見えているというわけではありません。イメージしてください。

この流れを憶えてください。重要です。最優先事項よ♪

↓ 呼び出された関数をコピーする

def kansuu(x):
    print(x)
    return

kansuu(0)

def kansuu(x):
    print(x)
    return

↓ コピーした関数のほうが使われる

def kansuu(x):  # ← 見本はいじらない
    print(x)  # ← 見本はいじらない
    return

kansuu(0)

def kansuu(0):
    print(0)
    return

0

↓ 関数の処理が終了したら、コピーした関数の全てが破棄される

def kansuu(x):
    print(x)
    return

None  # ← 戻り値 None に化けてプログラムは終了する

----- コピーした関数は破棄された -----

Chatpter.2 - 再帰関数のΨ難

再帰関数はみんなつまづく

再帰関数とは

【結論】再帰関数なんてものは存在しません

「再帰関数とは『自分自身を呼び出す関数』のことです。」

嘘だッ！！！！！

「SAIKI関数は、ありまーす！」

嘘だッ！！！！！

再帰関数を使ったプログラムを見てみます。

def kansuu(x):
    if x == 2:  # 再帰関数の終了条件
        return

    print(x)

    return kansuu(x + 1)  # ← ココに注目

kansuu(0)

0
1

戻り値を返す前に、kansuu(x + 1) を呼び出しています。
kansuu(x + 1) の戻り値が、今処理している関数の return の戻り値となるので、先に kansuu(x + 1) を呼び出して処理をします。

「・・・じゃあ今処理中の関数はどうなるの？」
「自身の関数を呼び出すという意味がよくわからない。」

皆、様々な理由でつまづきます。処理のイメージが掴めないからです。

関数はテンプレート再び！

関数はコピーして使う

Chatpter.1 で説明したものと同じ内容です。

もう一度この流れを見て理解してください。

↓ 呼び出された関数をコピーする

def kansuu(x):
  print(x)
  return

kansuu(0)

def kansuu(x):
    print(x)
    return

↓ コピーした関数のほうが使われる

def kansuu(x):  # ← 見本はいじらない
  print(x)  # ← 見本はいじらない
  return

kansuu(0)

def kansuu(0):
    print(0)
    return

0

↓ 関数の処理が終了したら、コピーした関数の全てが破棄される

def kansuu(x):
  print(x)
  return

None  # 関数が戻り値に化ける

----- コピーした関数は破棄された -----

再帰関数の解説

再帰関数は再帰しない

もう一度このプログラムを使って説明します。

def kansuu(x):
  if x == 2:  # 再帰関数の終了条件
    return
  print(x)
  return kansuu(x + 1)  # ← ココ

kansuu(0)

0
1

まず kansuu(0) で、関数を呼び出します。

呼び出された関数は、自身をコピーして、コピーを渡します。

def kansuu(x):
  if x == 2:
    return
  print(x)
  return kansuu(x + 1)

kansuu(0)

def kansuu(x):  # 新しいコピー
    if x == 2:
        return
    print(x)
    return kansuu(x + 1)

↓ 最初に、引数 0 を受け取る

def kansuu(0):  # 実行中
    if x == 2:
        return
    print(x)
    return kansuu(x + 1)

↓ 0 == 2 ではないので 0 を出力

def kansuu(0):  # 実行中
    if False:
        return
    print(0)
    return kansuu(x + 1)

0

↓ kansuu(0 + 1) → kansuu(1) となる

def kansuu(0):  # 実行中
    if False:
        return
    print(0)
    return kansuu(1)

return する前に、引数 1 の為の kansuu(x) が呼び出される
kansuu(x) は、kansuu(1) 用にテンプレート(自身)をコピーして、そのコピーを渡す。

def kansuu(0):  # 待機中
    if False:
        return
    print(0)
    return kansuu(1)

def kansuu(x):  # 新しいコピー
    if x == 2:
        return
    print(x)
    return kansuu(x + 1)

1

def kansuu(0):  # 待機中
    if False:
        return
    print(0)
    return kansuu(1)

def kansuu(1):  # 実行中
    if x == 2:
        return
    print(x)
    return kansuu(x + 1)

1 == 2

1

def kansuu(0):  # 待機中
    if False:
        return
    print(0)
    return kansuu(1)

def kansuu(1):  # 実行中
    if False:
        return
    print(1)
    return kansuu(x + 1)

1

kansuu(1 + 1)

kansuu(2)

def kansuu(0):  # 待機中
    if False:
        return
    print(0)
    return kansuu(1)

def kansuu(1):  # 実行中
    if False:
        return
    print(1)
    return kansuu(2)

return する前に、引数 2 の為の kansuu(x) が呼び出される
kansuu(x) は、kansuu(2) 用にテンプレートをコピーして、そのコピーを渡す。

def kansuu(0):  # 待機中
    if False:
        return
    print(0)
    return kansuu(1)

def kansuu(1):  # 待機中
    if False:
        return
    print(1)
    return kansuu(2)

def kansuu(x):  # 新しいコピー
    if x == 2:
        return
    print(x)
    return kansuu(x + 1)

2

def kansuu(0):  # 待機中
    if False:
        return
    print(0)
    return kansuu(1)

def kansuu(1):  # 待機中
    if False:
        return
    print(1)
    return kansuu(2)

def kansuu(2):  # 実行中
    if x == 2:
        return
    print(x)
    return kansuu(x + 1)

2 == 2

def kansuu(0):  # 待機中
    if False:
        return
    print(0)
    return kansuu(1)

def kansuu(1):  # 待機中
    if False:
        return
    print(1)
    return kansuu(2)

def kansuu(2):  # 実行中
    if True:  # ← 再帰関数の終了条件になる
        return
    print(x)
    return kansuu(x + 1)

None

return

def kansuu(0):  # 待機中
    if False:
        return
    print(0)
    return kansuu(1)

def kansuu(1):  # 実行中
    if False:
        return
    print(1)
    return None  # ← ココに戻る

def kansuu(2):

↓ 戻り値 None で呼び出し元に return する

def kansuu(0):  # 実行中
    if False:
        return
    print(0)
    return None  # ← ココに戻る

def kansuu(1):

↓ 戻り値 None で呼び出し元に return する

def kansuu(x):
  if x == 2:
    return
  print(x)
  return kansuu(x + 1)

kansuu(0)  # ← ココに戻る

def kansuu(0):  # 実行中
    if False:
        return
    print(0)
    return None

def kansuu(x):
  if x == 2:
    return
  print(x)
  return kansuu(x + 1)

None  # ← 戻り値 None に化ける

def kansuu(0):

これでこの再帰関数プログラムは正常に終了しました。

再帰関数の流れを掴む

まとめ

ざっくりとまとめました。

↓ スタート

def kansuu(x):
  if x == 2:
    return
  print(x)
  return kansuu(x + 1)

kansuu(0)

def kansuu(x): # 新しいコピー
    if x == 2:
        return
    print(x)
    return kansuu(x + 1)

kankuu(0)

def kansuu(0): # 実行中
    if False:
        return
    print(0)  # ← 0 を画面に出力
    return kansuu(0 + 1)

kankuu(1)

def kansuu(0): # 待機中
    if False:
        return
    print(0)
    return kansuu(1)

def kansuu(1): # 実行中
    if False:
        return
    print(1)  # ← 1 を画面に出力
    return kansuu(1 + 1)

kankuu(2)

def kansuu(0): # 待機中
    if False:
        return
    print(0)
    return kansuu(1)

def kansuu(1): # 実行中
    if False:
        return
    print(1)
    return kansuu(2)  # ③ ここに戻る

def kansuu(2): # 実行中
    if True:  # ① 終了条件になる
        return  # ② 戻り値 None で戻る
    print(x)
    return kansuu(x + 1)

def kansuu(0): # 待機中
    if False:
        return
    print(0)
    return kansuu(1)  # ② ここに戻る

def kansuu(1): # 実行中
    if False:
        return
    print(1)
    return None   # ① 戻り値 None で戻る

def kansuu(0): # 実行中
    if False:
        return
    print(0)
    return None   # 戻り値 None で最初に呼び出した所に戻る

def kansuu(x):
  if x == 2:
    return
  print(x)
  return kansuu(x + 1)

None  # ← 最初に呼び出した所

やっぱり自身を呼び出す関数ではありませんでしたね。
呼び出す関数のテンプレートをコピーして使う処理でした。
これがたとえ return kansuu2() だったとしても、kansuu2() の中の return で戻って来れば同じ流れになります。
何を呼び出しているかは問題ではありません。
処理中に関数の呼び出しに出遇い、その関数に引数を与えて実行しているだけなのです。
それは return の戻り値でなくても、どこに書いても同じです。
などで呼び出し先を複数作ったとしてもまったく同じです。
関数をコピーして処理し、終わったらコピーを破棄する。
関数はすべてこれをしているだけなのです。
コンピュータにとって、再帰しているかどうかなんてどうでもいい事なのです。

この流れが理解できたらもうなにも怖いものはありません。

Chatpter.3 - 再帰関数っていったい・・・

便利と言えば便利

再帰関数と呼ばれているものは「関数αの中で関数αを呼ぶ機関」です。
つまり、ただのループです。
これに最も近いのはです。

次の再帰関数プログラムをの書き方と比較してみます。

def kansuu(x):
    if x == 2:
        return
    print(x)
    return kansuu(x + 1)

kansuu(0)

0
1

これをで書くと・・・

def kansuu(x):
    while x < 2:
        print(x)
        x += 1
    return

kansuu(0)

0
1

まったく同じ結果が得られ、正しく終了されます。

共通する注目点は「ループを止める条件が必要」な点です。
再帰関数は「条件式が(基本的には)Trueの時」、のほうは「条件式が Falseの時」にループを抜けます。
そして上のどちらのプログラムも結果は同じでも、経過は大きく異なります。
のほうは関数を１つ呼び出し、関数の中の文でループしています。
再帰関数のほうは１つ関数を呼び出し、その関数が終了しないままもう１つ関数を呼び出すので、処理中の関数が呼び出した分だけどんどんメモリに溜まっていき、やがてメモリの容量をオーバーし、最悪システムダウンへと繋がるという恐れがあります。バ〇オハザードです。原〇事故です。
Python3 では、再帰関数のループ上限が 1000回に定められています。(回数を任意に指定したり、無限回に変更可能)
1000回を超えるとエラーになります。(逆にありがたい)

def kansuu(x):
    print(x)
    return kansuu(x + 1)
# 終了条件を書き忘れると・・・
kansuu(0)

Traceback (most recent call last):
  File "Main.py", line 5, in <module>
    kansuu(0)
  File "Main.py", line 3, in kansuu
    return kansuu(x + 1)
  File "Main.py", line 3, in kansuu
    return kansuu(x + 1)
  File "Main.py", line 3, in kansuu
    return kansuu(x + 1)
  [Previous line repeated 1000 more times]
  File "Main.py", line 2, in kansuu
    print(x)
RecursionError: maximum recursion depth exceeded while getting the str of an object

怒り具合が尋常ではありませんね。😹

再帰関数の利点はあえて言うならば「呼び出したい所で呼び出せる」というところでしょうか。
を使った場合は、例えばの中で条件分岐すると、途端に複雑になってしまいます。
再帰関数の場合は終了条件さえ付ければ、あとは呼び出す「関数１つ」を置きたい所に置くだけで済みますし、関数名が処理内容を表していますし、再帰かどうかということも一目でわかります。
そういう理由では、再帰関数が使えるのならば使ったほうが良いかもしれません。
もしダメならば、その時は違う方法を導入すれば良いですし。(「もしダメ」のリスクが高いですが😓)

再帰関数を使うとイケてる感が湧くかもしれませんが、必ずしも最良の方法というわけではありませんのでドヤ顔してやったりしないでくださいね。🤣