Neunomizuの日記

俺だけが俺だけじゃない

難しく考えたら負けかなと思っている

情報

難しく考えたら負けかなと思っている

tags: 情報

再帰関数難しく考えていないですか?

皆さんこんにちは.留学先でもピカチュウのTシャツを着て目立っていますピカチュウです(\not=不協和音)

どちらかと言ったらエキセントリック

東京は涼しいと聞いていますが,サンフランシスコの夏も一日の寒暖差が激しく上着が手放せません1 まぁそんなことはどうでもいいんですけど,今回は再帰関数に関して記事を書こうと思います

というのも,現地で再帰関数がよくわからない!というプログラミングを始めたての方がいるからです

教える前に記事にして一回まとめておこうというわけです

ゆるゆるに再帰関数の

  1. 再帰的定義(再帰関数は再帰関数で定義されている)
  2. 停止性(簡単になっているか,有限回で処理が終わるか)

を説明して,そこまで再帰関数が難しくないんじゃないかなと思ってもらえるような記事にしたいと思います

再帰的定義

再帰関数という名前の通り,再帰的定義を考えてみましょう

以下のPythonで書かれたコードを見てください

def fib(n)
    if n < 2:
        return n
    else:
        return fib(n-1) + fib(n-2)

ここで出てくるfibという関数は以下のように定義されたフィボナッチ数列の第n項を取り出すものです

$$ fib(n) = \begin{cases} 0 & (n=0) \\ 1 & (n=1) \\ fib(n-1) \cdot fib(n-2) & (otherwise) \end{cases} $$

fibという関数はfibという関数によって定義されていますね

これが再帰的定義で,自身で自身を定義していることが再帰関数の特徴です

そして,この再帰的定義は見てわかるように,最初の引数nを小さくしたn-1とn-2が使われています

後で,このことを考えるので頭の片隅においておいてください

停止性

???｢お前のものは俺のもの.俺のものも俺のもの｣

これはおそらく日本で一番有名なトートロジー2が使われた文章ですね(論理学の文脈で使っているわけではないので悪しからず) ｢これも再帰関数?｣と考えられそうな気もしますが違います

そもそも関数じゃないというのもありますが,その最も大きな差は停止性の有無です

またPythonのコードを見てみましょう

def fib(n)
    if n < 2:
        return n
    else:
        return fib(n-1) + fib(n-2)

ここではif < 2という部分でしっかりと関数が終了する条件が書かれています.

再帰的定義によってfibの引数であるnが小さくなり,最終的にn < 2で終了する, つまり有限回でこの関数が終了するように定義されています

一方&ャイ%ンのセリフでは｢お前のもの｣が｢俺のもの｣にはなりますが,｢俺のもの｣の定義が｢俺のもの｣なので一生に定義が完了しません

再帰関数がどんな感じなのかわかってくれましたか?

原作を見たら意味が全く違っていた...

分割統治法

問題を分割し,解決することを分割統治法と言います

再帰関数は分割統治法を使った関数です(もちろん有限回でおわらないのも再帰関数ですが,ある問題を解く再帰関数は必ずこのようになっている必要があります)

実際に関数が再帰的に使え,停止性がはっきりしているような問題に対してに使ってましょう

文字列をひっくり返して実感

文字を反転させる...

いろいろやり方はあると思いますが,

def inv(str):
    if str == "":
        return ""
    else:
        return str[-1] + inv(str[:-1])

ここでは以下のように考えることで実装しています

  1. 再帰的定義:答えとなる文字列は<すでに反転された文字列> + <反転される文字列の最後の文字>と考えることができます
  2. 停止性:反転させる文字列は徐々に小さくなり,反転させる文字列がなくなったときにこの関数は終わります

このように考えると上のようなコードを簡単に書くことが可能です

(Pythonではstr[::-1]で文字列を反転することができます.あくまで例のためです)

実際に問題を解く

｢具体例が少なすぎてわかりません!｣と言う人,すみません!

そんな方におすすめなサイトにLeetCodeというものがあります

データ構造とアルゴリズムを勉強･実践するのにはぴったりなサイトでこのページに再帰関数に関する情報,問題がまとまっているので実際に手を動かして身につけたいという人は是非楽しんでください

再帰関数が簡単だと思えるようになってくれたら嬉しいです

再帰関数を難しく考えたら負けだと思っている

  1. 7月17日(水) 21:13:21 PDT 現在↩

  2. https://en.wikipedia.org/wiki/Tautology_(language)↩