再帰

再帰とは

何かの中味に、それ自身が現れることを再帰という。 何かの定義に、それ自身が登場するようなものを再帰的定義 という。たとえば年齢に関する以下の二つの定義を比べてみよう。

  1. 年齢とは

    生まれた年月日から経過した年数のことである。
    ただし、1年に満たない月と日は切り捨てる。

  2. 年齢とは

    1年前の年齢に1を足したものである。
    ただし、1年前に生まれていない時の年齢は0歳である。

一般的な感覚でいえば、1.の定義が妥当だろう。しかし、 現実にわれわれが生活のなかで自分の年齢を数えているのは2.であることが多い。 たとえば、誕生日が来たときいちいち自分の生まれた年を引き算して毎年自分の 年齢を計算する人はまれだろう。昨日まで意識していた年齢に1を足して これから1年間の年齢とするだろう。その方が簡単だからである。

ここで出した例は、年齢の計算という非常に単純なものなので、1と2どちら でやろうとも大差ないのだが、もっと複雑な問題のなかには定式どおり解くよりも 再帰的な方式に則って解くと簡単になることが多い。

ここで気を付けるべきことがある。2.の定義は「年齢」の定義のなかにさらに 「年齢」という語があるので、それではいつまで経っても厳密に語の意味が定ま らないように感ずるが、そうではない。ただし書きがあるので、最終的に 「1年前に生まれていない時の年齢は0歳」という定義文により 曖昧さなく年齢が確定する。

再帰を利用したプログラミング

簡単な例をもうひとつ。プログラミングにしやすい例題を考えてみよう。 自然数に対する階乗の(再帰的でない)定義は以下のようになる。

  1. N の階乗とは

    1から N までのすべての自然数を掛けたもの

これを再帰的定義に直すと以下のようになる。

  1. N の階乗とは

    N-1 の階乗と N を掛けたものである。
    ただし、1の階乗は1である。

それぞれの定義をRubyのメソッドにすると以下のようになるだろう。

fact1.rb

# Nの階乗を求めるメソッド(定義1)

def factorial(n)
  ans = 1
  i = 1
  while i <= n
    ans *= i
    i += 1
  end
  ans
end

fact2.rb

# Nの階乗を求めるメソッド(定義2)

def factorial(n)	# nのfactorial(階乗)とは
  if n <= 1		# nが1なら
    1			# 答は1
  else			# そうでなければ
    n * factorial(n-1)	# n と factorial(n-1)を掛けたもの
  end
end

定義1によるメソッドの動きに関しては、これまで学習したので 説明を省略し、定義2によるメソッドについて考える。 定義2のプログラム中下線を施した部分が 再帰呼び出しとなっている。

たとえば、定義2のときに、factorial(5) と 呼び出した場合を考えよう。

def factorial(n)	# ←n=5
  if n <= 1		# 5 > 1 なので
    1			# ここには来ない
  else			# こっち↓
    n * factorial(n-1)	# 5 と factorial(5-1)を掛けたもの
  end
end

n=5なので、1よりも大きくelse節内が評価される。 すると、5 * factorial(5-1) を計算することになる。 この時点ではfactorial(5-1)の値はまだ分からない。 factorial(4) が呼ばれる。

def factorial(n)	# ←n=4
  if n <= 1		# 4 > 1 なので
    1			# ここには来ない
  else			# こっち↓
    n * factorial(n-1)	# 4 と factorial(4-1)を掛けたもの
  end
end

n=4なので、1よりも大きくelse節内が評価される。 すると、4 * factorial(4-1) を計算することになる。 ここでまた、factorial(3) が呼ばれる……。という ことを繰り返すうちに、nがひとつずつ減っていき、 最終的にfactorial(1)が呼ばれ、factorial メソッドは1を返す。これを図式化すると以下のようになる。

はじまり    おわり
  ↓         ↑
factorial(5)    ←(factorial(5)=5*24=120)
  ↓             ↑
  5 * factorial(4)    ←(factorial(4)=4*6=24)         ↑
        ↓             ↑
        4 * factorial(3)    ←(factorial(3)=3*2=6)
              ↓             ↑
              3 * factorial(2)       ←(factorial(2)=2*1=2)
   ↓               ↓                ↑
                    2 * factorial(1)  ↑
                          ↓          ↑
                          1 -----------+

実際にコマンドラインから利用できるプログラムに直して 実行してみよう。

factorial.rb

#!/usr/koeki/bin/ruby
# coding: utf-8

def factorial(n)
  if n <= 1
    1
  else
    n * factorial(n-1)
  end
end

if ARGV[0] == nil
  STDERR.puts "階乗を計算したい数を指定して下さい"
  STDERR.puts "例: ./factorial.rb 5"
  exit 0
end

n=ARGV[0].to_i
printf("%dの階乗は%dです\n", n, factorial(n))

再帰的メソッドのポイント

メソッドを再帰的に定義する場合、以下の点に注意する。

階乗計算は再帰を用いず、ループを利用しても十分に簡単であるので、 本来はループ処理で定義するのが自然である。再帰処理は実際には 複雑な問題を簡単にして解く場合に有効となる。次節ではそのような例を 見ていこう。

本日の目次へ