再帰関数の作り方 #Python

再帰関数を作るのは難しい

再帰関数を作るのは難しいですよね．
再帰関数に関する解説記事は多いですが，すでにある再帰関数のコードの説明ばかりで，作成方法について解説している記事は少ない印象です．．

再帰関数の作り方に関する記事を調査すると，ここの英語記事では，再帰関数を作るフローをわかりやすく解説していました．英語記事の内容を自身で噛み砕いて意訳してみたので，共有したいと思います．

1. 再帰関数とは

一言でいえば，関数の中に自分自身の呼び出しが含まれている関数．詳細は，他の記事を参考にしてください．

2. 再帰関数を構成する２つの機能

まず，再帰関数を構成する機能を理解しましょう．
再帰関数を構成するためには，２つの機能が必要です：

停止的な機能：自身の関数から出る部分
再帰的な機能：関数がそれ自身を呼ぶ部分

例えば，文字列を反転する再帰関数を考えてみます．上記の２つの機能にわけてみます：

def reverse_string(str1):
    #停止的な機能
    if len(str1)<2:
        return str1

    #再帰的な機能
    return reverse_string(str1[1:])+str1[0]

停止的な機能の部分をコードに変換することは比較的簡単だと思います．
一方，再帰的な機能をコードに変換することは難しいはずです．
そこで，この再帰的な機能をコードに変換するフローについて説明します．

3. 再帰的な機能をコードに変換するフロー

以下のフローで再帰的な機能をコードに変換します：

再帰関数で解く問題を決める．
解く問題よりワンステップ簡単な問題を考える．
ワンステップ簡単な問題に対して，自身がこれから作る関数によって解くことができると全身全霊で信じる！
3からワンステップ簡単な問題の解ができる(と全身全霊で信じている)．その解をsol1とする．
sol1を用いて，解く問題の解(solとする)を表現する．

解く問題をn個の問題に関する問題とすると，ワンステップ簡単な問題はn-1個に関する問題のイメージ．前文での説明の意味を5章の例題で具体的に示してみます．

4. 再帰関数を作るフロー

3章では，再帰的な機能をコードに変換するフローを作成しました．
それでは，再帰関数を構成するフローをまとめてみます．

再帰関数名を作成
停止的な機能をコードに変換
再帰的な機能をコードに変換
1. 再帰関数で解く問題を決める．
2. 解く問題よりワンステップ簡単な問題を考える．
3. ワンステップ簡単な問題に対して，自身がこれから作る関数によって解くことができると全身全霊で信じる！その関数をfunと名付けよう．
4. funからワンステップ簡単な問題の解ができる．その解をsol1とする．
5. sol1を用いて，解く問題の解(solとする)を表現する．

5. 例題

以下の例題を解く再帰関数を，３章のフローにそって作成しましょう．

問題：文字列を反転する．（ex:abc→cba）

反転したい文字列をstr1とします．
(Pythonでコーディングしています．)

再帰関数名をreverse_stringとする：
```
def reverse_string(str1):
```

停止的な機能をコードに変換：

def reverse_string(str1):
    #停止的な機能
    #文字列の長さが1なら関数からでる．
    if len(str1)<2:
        return str1

再帰的な機能をコードに変換

解く問題：文字列str1を反転する

ワンステップ簡単な問題：「文字列stringから先頭の１文字を削除した文字列」(これをstr1_remとする)を反転する．ここでは，str1_remをコードで表現してみる：

def reverse_string(str1):
    #停止的な機能
    #文字列の長さが1なら関数からでる．
    if len(str1)<2:
        return str1

    #文字列str1から先頭１文字を削除
    str1_rem=str1[1:]

ワンステップ簡単な問題に対して，自身の関数(reverse_string)によって解くことができると全身全霊で信じる！

ワンステップ簡単な問題に対するreverse_string関数によって得られる解をsol1である(と全身全霊で信じている)．すなわち，sol1=reverse_string(「文字列stringから先頭の１文字を減らした文字列」)である(と全身全霊で信じている)：

def reverse_string(str1):
    #停止的な機能
    #文字列の長さが1なら関数からでる．
    if len(str1)<2:
        return str1

    #文字列str1から先頭１文字を削除
    str1_rem=str1[1:]

    #reverse_stringはstr1_remを反転できると全身全霊で信じている．
    sol1=reverse_string(str1_rem)

sol1から，解く問題の解（sol）を表現する．「文字列stringの先頭の文字」をsol1の後ろにつけると，solとなる．数学的に表現すると，sol=sol1+「文字列stringの先頭の文字」である：

def reverse_string(str1):
    #停止的な機能
    #文字列の長さが1なら関数からでる．
    if len(str1)<2:
        return str1

    #文字列str1から先頭１文字を削除
    str1_rem=str1[1:]

    #sol1がstr1_remを反転した文字列であると全身全霊で信じている．
    sol1=reverse_string(str1_rem)

    #sol1からsolを表現
    sol=sol1+str1[0]
    
    return sol

不思議なことに，これで再帰関数ができています！．

上記のコードを短縮すると，

def reverse_string(str1):
    if len(str1)<2:
        return str1
    return reverse_string(str1[1:])+str1[0]

となります．

6. 感想

日本語の記事がわかりにくい場合は，英語の記事に詳細が書かれていることが多いです．慣れないうちは，上記のフローを文章にしてからコーディングすることをお勧めします．最初は，簡単な例題で練習しましょう．例えば，配列の要素をすべて表示する問題であったり．

謝辞

コメント頂いた方，修正していた方に感謝申し上げます．