再起関数の作り方 - 暇人万覚帳

背景

全探索のコードを書く際に，再帰関数を使用する方法がある．再帰関数に関する解説記事は多いが，作り方について納得できる記事がなかった．そのときに，英語記事を読んで，再帰関数の作り方を理解したので共有したいと思う．

1. 再起関数とは

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

2. 再起関数を作るフロー

以下のフローで再帰関数を作る.

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

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

※再帰関数をループするためには，一旦自身の関数から抜け出して自身の関数に戻る必要がある．そのため，自身の関数から出る必要があり，さらに，自己の関数内に自己の関数を含む必要がある．また，再起関数のループを終えるよう，例外処理を加える必要もある．

3 例題

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

それでは，上記のフローに従って再帰関数を作ってみよう．ある文字列(ex: abc)をstr1と名づける．

解く問題：文字列str1を反転する
ワンステップ簡単な問題：「文字列stringから先頭の１文字を減らした文字列」(これをstr1_remとする)を反転する
ワンステップ簡単な問題に対して，自身がこれから作る関数によって解くことができると仮定する．その関数名をreverse_stringとしよう．
ワンステップ簡単な問題に対するreverse_string関数によって得られる解をsol1とする．すなわち，sol1=reverse_string(「文字列stringから先頭の１文字を減らした文字列」)である．
sol1から，解く問題の解（sol）を表現する．「文字列stringの先頭の文字」をsol1の後ろにつけると，solとなる．数学的に表現すると，sol=sol1+「文字列stringの先頭の文字」である．

上記をもとに，コードを書いてみる（「2. 再起関数を作るフロー」にある※も考慮してください）．

def reverse_string(str1):
    if len(str1)<2:
        return str1
    
    #文字列stringから先頭の１文字を減らした文字列
    str1_rem=str1[1:]
    
    #str1を反転
    sol1=reverse_string(str1_before)
    
    #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]

となる．

3. 感想

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

追記

1. 2020/04/07　文章を修正
2. 2020/04/13  pythonのコードを挿入