再帰の基本

2013年3月30日：アルゴリズム

再帰を使うと、プログラムを完結にかけたり、効率的に計算できたりします。

ここでは、再帰について解説して再帰を使いこなせるようになることを目的とします。

階乗を再帰で計算する

階乗とは

5!=5☓4☓3☓2☓1

というような演算です。これを再帰を使って計算します。計算には

  • 0!=1
  • n>0ならばn!=n☓(n-1)!

ということを使います。２つ目のところに階乗の計算に階乗を使っていますね。これが再帰です。では組んでいきます。

プログラムの実行手順を確認する

先ほど組んだプログラムの実行手順を確認していきます。

まず、func(5)として考えます。func(5)を起動すると、

5☓func(4)

が返されます。func(4)がわからないので計算すると

4☓func(3)

となります。これを繰り返すと

  • 5☓func(4)
  • 4☓func(3)
  • 3☓func(2)
  • 2☓func(1)
  • 1☓func(0)

となりfunc(0)=1なので、ここでようやくとまります。そして今度は逆をたどり

  • func(1)=1☓func(0)=1☓1=1
  • func(2)=2☓func(1)=2☓1=2
  • func(3)=3☓func(2)=3☓2=6
  • func(4)=4☓func(3)=4☓6=24
  • func(5)=5☓func(4)=5☓24=120

と計算したい値が得られます。

一旦進めて、再び帰ってくるので再帰と呼びます。

最後に

再帰はあまり使う機会がないと思いますが、再帰的に定義されている場合は簡単に組めるので有効です。

一方、再帰的に組むと、無駄な計算が多くなる可能性があるので注意しましょう。

著者：安井 真人(やすい　まさと)

TOP