はじめまして。リンクアンドモチベーションで[モチベーションクラウド] (https://www.motivation-cloud.com/)の開発をしている[@ohtatakato] (https://qiita.com/ohtatakato)です。
この記事は、「[モチベーションクラウド Advent Calendar 2018] (https://qiita.com/advent-calendar/2018/mcs)」の記事となります。
新卒2年目から未経験で急遽エンジニアとなり、現場に入ってまだ1ヶ月の私ですが、研修を通して学んだことをまとめていきます。
この記事では、再帰プログラムとは何なのかが分かっていない方の為に具体例を示しながらなるべく分かりやすく説明しようと思います。
再帰プログラムとは
再帰とはwikipediaに下記のように記載があります。
再帰（さいき）は、あるものについて記述する際に、記述しているものそれ自身への参照が、その記述中にあらわれることをいう
つまり、再帰プログラムとはプログラム中で自身への参照をしているプログラムのことを言うわけですが、私はこれだけではいまいち何を言っているのか分かりませんでした。
具体例 ： クリスマスツリーに星を飾る
クリスマスツリーに星を一つずつ飾ってn個の星が飾られた状態をつくります。
仮に10個の星が箱の中に入っていたとして、ツリーに星を飾る回数を数えるときに、
下記のように考えることができます。
「10個の星を飾り付けるためには9個の星を飾り付けた状態のツリーにさらに1個星を飾れば良い」
これを数式で表すと下記のように書けます。
kazatteru_hoshi(n)でn個の星が飾られた状態を示すとすると
kazatteru_hoshi(10) = kazatteru_hoshi(9) + 1
このように10個の星を飾るためには9個の星が飾られている必要があり、
同様に9個の星を飾るためには8個の星が飾られている必要があります。
まさにこれが再帰的な試行なのです。
n個の星を飾る行為は下記のように記述することができます。
def kazatteru_hoshi(n)
if n < 1
return 0
else
return kazatteru_hoshi(n - 1) + 1
end
end
※nはintとする
再帰プログラムは漸化式だった！
ここまで学習してみて、再帰プログラムを作成する際には高校数学の漸化式の作成と同様のことをしていることに気がつきました。
今回のクリスマスツリーを飾る試行の漸化式は下記のようになります。
f(1) = 1
f(n) = f(n-1) + 1
この漸化式を解くとf(n) = n
wikipediaで「漸化式」を調べてみると
漸化式（ぜんかしき、英: recurrence relation; 再帰関係式）は、各項がそれ以前の項の函数として定まるという意味で数列を再帰的に定める等式である。
つまり、高校生の頃に学んだ漸化式を作成することができれば、再帰プログラムを組むことは容易にできるということです。
↓フィボナッチ数列の漸化式も再帰で書けますね
f(0) = 0
f(1) = 1
f(n) = f(n-2) + f(n-1)
def fibo(num)
if num < 0
return "numは0以上の整数"
else
case num
when 0
return 0
when 1
return 1
else
return fibo(num-2) + fibo(num-1)
end
end
end
注意点
再帰プログラムにおいて自身を呼び出す回数が多くなると計算量が膨大になってしまう可能性があるので注意が必要です。
これに関してはお正月休みに詳しくまとめようと思います。
最後に
モチベーションクラウドは社員と複数のパートナー企業様、フリーランスの方の混合チームで開発しています。
エンジニアになる以前はスクラムマスターとして携わっていたのですが、その時からプロダクトだけでなく、その根底にあるチーム創りを大切にしています。
興味がある方は[モチベーションクラウド Advent Calendar 2018] (https://qiita.com/advent-calendar/2018/mcs)の下記記事をご覧ください。
[スクラムマスターを経験して味わった成功体験と失敗体験] (https://qiita.com/kiiiiita/items/7f7ce7b8fdfb7a6a5b2b)
[組織で技術的負債に立ち向かうための取り組み] (https://qiita.com/cawpea/items/fd0c6633cd2b0c919d7a)