再帰とは

再帰 (recursion) とは，あるものの定義にそれ自身が使われることをいいます． 例えば，0 以上の整数 n の階乗 n! は次のように再帰的に定義することができます．

n! = (n-1)! * n

10! を計算するには 9! に 10 をかければよく，9! を計算するには 8! に 9 をかければよい，といった具合です． もちろん，これを際限なく続けていってもきりがないので，再帰的な繰り返しを中断する条件が必要です（これを「停止条件」といいます）． 階乗の場合は 0! を 1 と決めておきます． こうしておけば，0 以上の整数 n について n! を計算することができます．

まとめると，n の階乗は次のように定義できます．

n! = (n-1)! * n     (n >= 1)
0! = 1

これをプログラムにすることを考えてみましょう．

階乗

Fortran 90 では関数やサブルーチンの中で自分自身を呼び出し，再帰的な手続きを簡単に書くことができます． 以下に，再帰的に n! を計算する関数 fact() の例を示します．

recursive real(8) function fact(n) result (ret)
  implicit none
  integer, intent(IN) :: n

  if (n >= 1) then
     ret = fact(n-1) * n
  else if (n == 0) then
     ret = 1
  end if

  return
end function fact

自分自身を呼び出していること以外，関数の中身に特別なことはありませんが，以下の2つの点に注意してください．

  1. 関数定義の冒頭に「recursive」というキーワードを付ける．
  2. 関数名への代入ができないので，戻り値の設定には result(戻り値変数) を利用する．

ハノイの塔

ハノイの塔は次のようなゲームです． 台に3本の棒 A, B, C が固定されています． 最初，A の棒に何枚かの円盤が棒を通して重ねられています． 円盤は下にいくほど半径が大きくなっています． 下の図は3枚の円盤 1, 2, 3 が棒 A に刺さっている状態を示しています．

    1         |          |
   222        |          |
  33333       |          |
--------------------------------
    A         B          C

このとき，次の規則にしたがってすべての円盤を A から B に移動させてください．

これを解くプログラムを考えてみましょう．

円盤が1枚のとき

円盤1を B に移動させれば終わりです．

    1         |          |
--------------------------------
    A         B          C

    |         1          |
--------------------------------
    A         B          C

円盤が2枚のとき

円盤が2枚の時も簡単です． まず円盤1を C に移します． 円盤2を B に移してから，円盤1を B に移せば完成です．

    1         |          |
   222        |          |
--------------------------------
    A         B          C

    |         |          |
   222        |          1        円盤 1 を C に移す
--------------------------------
    A         B          C

    |         |          |
    |        222         1        円盤 2 を B に移す
--------------------------------
    A         B          C

    |         1          |
    |        222         |        円盤 1 を B に移して完成
--------------------------------
    A         B          C

円盤が3枚のとき

円盤が3枚のときは，上の2枚をひとまとまりと考えることによって，円盤が2枚の場合と同じように考えることができます．

    1         |          |
   222        |          |
  33333       |          |
--------------------------------
    A         B          C

    |         |          |
    |         |          1
  33333       |         222       円盤 1, 2 を C に移す
--------------------------------
    A         B          C

    |         |          |
    |         |          1
    |       33333       222       円盤 3 を B に移す
--------------------------------
    A         B          C

    |         1          |
    |        222         |
    |       33333        |        円盤 1, 2 を B に移して完成
--------------------------------
    A         B          C

何かだまされているような気がするかもしれませんが，2枚の円盤を正しい手順によって別の棒に移せることはすでに確かめてあるので，これで問題ありません．

同様に，円盤が n 枚の場合は，上の n-1 枚をひとまとまりと考えることによって，円盤を移動させることができます．

プログラム

以上の考えをプログラムにすると次のようになります．

!------------------------------------------------------------
! ハノイの塔
! n 枚の円盤を棒 a から棒 b に移す．
! 3つ目の棒 c は円盤の一時的な置き場にしてよい．
!------------------------------------------------------------
recursive subroutine hanoi(n, a, b, c)
  implicit none
  integer, intent(IN) :: n
  character :: a, b, c

  if (n == 0) return            ! 円盤がない場合は何もしない

  call hanoi(n-1, a, c, b)      ! 上の n-1 枚を a から c に移す
  write(*,*) n, a, b            ! 円盤 n を a から b に移す
  call hanoi(n-1, c, b, a)      ! n-1 枚の円盤を c から b に移す

  return
end subroutine hanoi

!------------------------------------------------------------
! ハノイの塔のメインプログラム
!------------------------------------------------------------
program main
  implicit none
  integer :: n

  write(*,*) 'Input N:'
  read(*,*) n

  call hanoi(n, "A", "B", "C")

  stop
end program main

次のリンクに詳しい説明がありますので，上のプログラムとよく比較してみましょう．

本日の課題

フィボナッチ数列

フィボナッチ数列 fib(n) は次のように再帰的に定義される．

fib(1) = 1
fib(2) = 1
fib(n) = fib(n-1) + fib(n-2)

以下のプログラムを完成させ，fib(20) の値を求めよ．

!------------------------------------------------------------
! 再帰的に定義したフィボナッチ数列
! 初項は fib(1) = 1, fib(2) = 1 とした．
!------------------------------------------------------------
recursive integer function fib(n) result (ret)
  implicit none
  integer, intent(IN) :: n

  if (n == 1) then
     ret = 1
     return
  end if

  if (n == 2) then
     !*****************************************************************
     ! この部分を自分で考えましょう
     !*****************************************************************
  end if

  !*****************************************************************
  ! この部分を自分で考えましょう
  !*****************************************************************

  return
end function fib

!------------------------------------------------------------
! メインプログラム
!------------------------------------------------------------
program main
  implicit none
  integer :: fib, n

  do n = 1, 30
     write(*,*) fib(n)
  end do

  stop
end program main

自然数の和

正の整数 n 以下のすべての自然数の和 sigma(n) は次のように再帰的に定義される．

sigma(0) = 0
sigma(n) = sigma(n-1) + n

sigma(n) を Fortran 90 の再帰関数として定義し，sigma(100) の値を求めよ．