再帰関数の作り方

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

再帰関数の作り方に関する記事を調査すると，[ここの英語記事](https://medium.com/@daniel.oliver.king/getting-started-with-recursion-f89f57c5b60e)では，再帰関数を作るフローをわかりやすく解説していました．英語記事の内容を自身で噛み砕いて意訳してみたので，共有したいと思います．

## 1. 再帰関数とは

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

## 2. 再帰関数を構成する２つの機能
まず，再帰関数を構成する機能を理解しましょう．
再帰関数を構成するためには，２つの機能が必要です：
1. **停止的な機能**：自身の関数から出る部分
2. **再帰的な機能**：関数がそれ自身を呼ぶ部分

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

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

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

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

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

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

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

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

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

0. 再帰関数名を作成
1. 停止的な機能をコードに変換
2. 再帰的な機能をコードに変換
    1. 再帰関数で<font color="Red">解く問題</font>を決める．
    2. <font color="Red">解く問題</font>より<font color="Blue">ワンステップ簡単な問題</font>を考える．
    3. <font color="Blue">ワンステップ簡単な問題</font>に対して，自身がこれから作る関数によって解くことができると**全身全霊で信じる**！その関数をfunと名付けよう．
    4. funから<font color="Blue">ワンステップ簡単な問題</font>の解ができる．その解をsol1とする．
    5. sol1を用いて，<font color="Red">解く問題</font>の解(solとする)を表現する．
 
## 5. 例題
以下の例題を解く再帰関数を，３章のフローにそって作成しましょう．

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

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

0. 再帰関数名をreverse_stringとする：

    ```python
    def reverse_string(str1):
    ```

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

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

2. 再帰的な機能をコードに変換
    1. <font color="Red">解く問題</font>：文字列str1を反転する
    2. <font color="Blue">ワンステップ簡単な問題</font>：「文字列stringから先頭の１文字を削除した文字列」(これをstr1_remとする)を反転する．ここでは，str1_remをコードで表現してみる：

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

            #文字列str1から先頭１文字を削除
            str1_rem=str1[1:]
        ```
    
    3. <font color="Blue">ワンステップ簡単な問題</font>に対して，自身の関数(reverse_string)によって解くことができると**全身全霊で信じる**！
        
    4. <font color="Blue">ワンステップ簡単な問題</font>に対するreverse_string関数によって得られる解をsol1である(と全身全霊で信じている)．すなわち，sol1=reverse_string(「文字列stringから先頭の１文字を減らした文字列」)である(と全身全霊で信じている)：

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

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

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

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

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

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

となります．

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

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