第 4 回再帰処理

本日の内容

4-1. 再帰処理
4-2. C++ 言語固有の話(2)
4-3. タートルグラフィックのクラス
4-4. Windows のプログラミング
4-5. 再帰処理によるグラフィック
4-6. Java での再帰グラフィック

このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。

4-1. 再帰処理

同じ関数の中で自分自身の関数を呼び出すことができます。これを再帰処理と言います。今回は再帰処理の有用性について説明します。

問題を解決する際に、問題を分解し、分解した部分に同じ解法を適用できるような場合があります。その時、この再帰処理は有効です。例えば、前々回まで取り上げていた「階乗」の計算では、 n の階乗は for 文を用いてましたが、次のような漸化式でも書けます。

{\begin{matrix} n! = n (n - 1)! \\ 0! = 1 \end{matrix}

これを C の関数にすると次のようになります。


int factor(int n){
  if(n==0){return 1;}
  else{ return n*factor(n-1); }
}

この関数の場合、 for 文で単純に書けるので、再帰処理にする必要はありません。しかし、組合せの数ではこの再帰処理が有効です。実は、先日紹介した factor をもとに計算する組合せの数では $_{20} C_{2} = \frac{20 * 19}{2 * 1} = 190$ もオーバフローして計算できません。これは、内部で factor を使い、 $\frac{20!}{2! 18!}$ を求めているからです。この中の $20!$ は $10^{18}$ を超えます。つまり、結果は 190 という小さい値ですが、途中で 20! という計算がおかしくなるほど巨大な数を使ってしまうので、正常に計算できなくなります。そこで、組合せの数は factor を使わずに計算する必要があります。

組合せの数をパスカルの三角形を使って計算する方法を考えます。パスカルの三角形とは次のような数表のことです。

        1   1
      1   2   1
    1   3   3   1
  1   4   6   4   1
1   5  10  10   5   1

各値は上の左右の値を足したものになっています。そして、その値は組合せの数を表しています。一番上は $_{1} C_{0}$ と $_{1} C_{1}$ を、二列目は $_{2} C_{0}$ , $_{2} C_{1}$ , $_{2} C_{2}$ を表しています。もともと、n 個のものから m 個のものを取り出す組合せの数は、ある n 個の中の 1 つのものに注目して、 (1) そのものを選んだ時の組合せの数と (2)それを選ばなかった時の組合せの数を足したものになるはずです。つまり、それは (1)n-1 個の中から m-1 個を取り出す組合せの数と (2)n-1 個の中から m 個を取り出す組合せの数の和になります。式で書くと $_{n} C_{m} =_{n - 1} C_{m - 1} +_{n - 1} C_{m}$ となります。なお、 $_{n} C_{0} = 1$ , $_{n} C_{n} = 1$ とします。これを C 言語で計算させるプログラムは次の通りです。


int combination(int n, int m){
  if(m==0){ return 1; }
  else if(n==m){ return 1; }
  else{ return combination(n-1,m-1)+combination(n-1,m); }
}

このようにすると計算の途中で行われるのは足し算のみなので巨大な値は扱いません。従って、大きな値でも求めることができるようになります。

演習4-1

上の combination を使って、組合せの数 $_{5} C_{2}$ , $_{20} C_{2}$ を求めなさい。

演習4-2

フィボナッチ数列は次のように定義されます。 f(20), f(40), f(60) を求めなさい。

f (0) = 1

f (1) = 1

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

なお、この計算では一度計算した値を何度も計算し直すので効率が悪いです。例えば、グローバルな配列変数を用意し初期値を 0 としておいて、 0 だったらその値を計算して配列変数に代入し、 0 でなければ配列変数の値を使うようにすると f(40) 程度まで瞬時に求められるようになります。

また、 f(n) を求める時、f(i) が何回計算されるか、さらに、再帰処理が行われるかを n の関数で求めなさい。

演習4-3

アッカーマン関数は次のように定義されます。この関数は原始帰納関数という関数のクラスでは計算できないほど値が大きくなる関数です。この関数に対し、小さなパラメータの値を計算し、a(0,m), a(1,m), a(2,m), a(3,m) などがどのような関数になるか考えなさい。

{\begin{matrix} a (0, m) = m + 1 \\ a (n, 0) = a (n - 1, 1) \\ a (n, m) = a (n - 1, a (n, m - 1)) \end{matrix}

演習4-4

ハノイの塔とは重ねた円盤を動かすパズルです。大きさが一回りずつ違う円盤を大きい順に下から並べます。そして、次のルールでその円盤の山を移動させます。

一度には一枚しか動かせない。
移動可能な場所は、現在位置を含み三箇所
小さい円盤の上に大きい円盤を置くことはできない

以下に 3 枚での例を示します。

	a	b	c
1	= == === --a--	--b--	--c--
2	== === --a--	= --b--	--c--	move 1 from a to b
3	=== --a--	= --b--	== --c--	move 2 from a to c
4	=== --a--	--b--	= == --c--	move 1 from b to c
5	--a--	=== --b--	= == --c--	move 3 from a to b
6	= --a--	=== --b--	== --c--	move 1 from c to a
7	= --a--	== === --b--	--c--	move 2 from c to b
8	--a--	= == === --b--	--c--	move 1 from a to b

この解法を再帰的に考えます。もし、hanoi(n-1,'a','b','c') が n-1 枚の円盤を a から b へ移動する解法を出力するとします(c はもう一つの領域)。すると、 n 枚の円盤を a から b へ移動する解法は次のように考えられます。

まず、 n の上に乗っている n-1 枚の円盤を a から c へ移動します。つまり hanoi(n-1,'a','c','b')
そして、n を a から b へ移動します。 move n from a to b
最後に c にある n-1 枚の円盤を b に移します。 hanoi(n-1,'c','b','a')

このようにすると hanoi(n,'a','b','c') の解法を出力します。 hanoi(3,'a','b','c') と hanoi(4,'a','b','c') の解法を求めなさい。

4-2. C++ 言語固有の話(2)

関数の呼び出し方

関数の呼び出し方には、理論上三種類あります。

値呼び出し: 呼び出された関数の中で、ローカル変数に引数の値をコピーして使う。
変数呼び出し: 引数で指定した変数を、呼び出された関数は使用できる。
名前呼び出し: 引数に式を書いた場合、その引数の値が必要かどうかを関数の中で判断するため、式のまま関数に引き継ぐ。

このうち、C 言語では値呼び出ししか出来ないことは前回説明しました。しかし、C++ 言語では変数呼び出し(C++ 用語では参照呼び出し) ができます。関数定義の際、引数の定義で変数の前に & を付けると参照呼び出しであることが指定できます。次のプログラムは C 言語ではコンパイルできませんが、 C++ ではコンパイルでき、予想通りの動作をします。


#include <stdio.h>
void swap(int &a, int &b){
  int c;
  c=a;
  a=b;
  b=c;
  return;
}
int main(void){
  int a=3,b=4;
  printf("%d, %d\n",a,b);
  swap(a,b);
  printf("%d, %d\n",a,b);
  return 0;
}

なお、 swap は別に引数が int である必然性はないので、本来はテンプレートで定義すべきでしょう。


#include <stdio.h>
template swap <typename T>
void swap(T &a, T &b){
  T c;
  c=a;
  a=b;
  b=c;
  return;
}
int main(void){
  int a=3,b=4;
  printf("%d, %d\n",a,b);
  swap(a,b);
  printf("%d, %d\n",a,b);
  return 0;
}

ユーザ定義定数

C++ 言語には const という定数を宣言する演算子があります。これを使うと、値を変更しないことを宣言でき、不用意な代入操作によるプログラムミスなどをコンパイル時にエラーとして通知してもらえるようになります。

定数変数

C 言語で定数を宣言するには #define を用いました。 #define で宣言する定数には型がないという欠点があります。 C++ では const を添えて、変数を初期化しながら宣言することで型情報を持った定数を宣言できます。

例4-1


#include <iostream>
int main(void){
  const int isan = 3;
  const double dsan = 3;
  std::cout << isan/2 << dsan/2 << std::endl;
  return 0;
}

またポインタ宣言に関しては * の前に const を書くと参照先の値を変更できなくなり、また、 * の後に書くとポインタ自体を変更できなくなります。

例4-2


const char *p="abcde";
char * const q="abcde";
char r[]="abcde";
char * const s=r;
++p ;        //OK
// *p='x';   //NG
//q++;       //NG
//*q='y';    //NG "" で指定した文字列自体は
             //  const char * 型なので変更できない
r[0]='y';    //OK "" で初期化した文字配列は変更できる
//s++;       //NG
*s='z';      //Ok

const 引数

関数定義の際、(特に参照型で)const を宣言すると関数内で値を変更できなくなります。

例4-3


int plusone(const int& x){
  // x++; // NG;
  return x+1; //Ok;
}

const メンバ関数

メンバ関数の定義でメンバ関数名の後に const を指定すると、メンバ変数を変更しないメンバ関数を定義できます。

例4-4


class X {
  int y;
  int plusone(void) const {
    // y++; // NG
    return y+1; // Ok
  }
};

このようにプログラムミスを無くすため、値を変化させないものには const を指定するようにします。

4-3. タートルグラフィックのクラス

実用的なクラスの例として、多少高級なグラフィックのパッケージを考えます。ここで示すタートルグラフィックというのは、次のようなコマンド群からなるものです。

原点を ○,○ という座標に設定
○歩足跡を付けて前進
○度回転
○歩足跡を付けずに移動

これを点から点へ線を引くことしかできない低レベルなグラフィックから実現することを考えます。クラス Turtle のメソッドとして次のものが考えられます。

void home(int x, int y)
void forward(double n)
void turn(double d)
void skip(double n)

クラスの宣言部は次のようになるはずです。


class Turtle {
private:
  double x;
  double y;
  double angle;
public:
  Turtle();
  ~Turtle();
  void home(int _x, int _y);
  void forward(double n);
  void turn(double d);
  void skip(double n);
};

このうち、コンストラクタ Turtle::Turtle() はグラフィックの初期化、デストラクタ Turtle::~Turtle() はグラフィックの後処理をします。

演習4-5

以下の空欄を埋めて Turtle クラスのメソッドを実装しなさい。


#include <cmath>
#include グラフィック 
// 次の節で Windows 用に改造します。
void Turtle::home(int _x, int _y){
   // x, y に値を代入
}
void Turtle::forward(double n){
  double newx, newy;
  // newx, newy を計算
  line(x,y,newx,newy);
  // x,y に newx, newy を代入
}
void Turtle::turn(double n);
  // angle に n を足す(ラジアンに直す)
}
void Turtle::skip(double n){
  double newx, newy;
  // newx, newy を計算
  // x,y に newx, newy を代入
}

4-4. Windows のプログラミング

Windows の UI はアイコンにメッセージを送ることで操作するので、一応オブジェクト指向になっています。しかし、内部での処理はオブジェクト指向になってなく、次のようなプログラミング技術(イベントドリブン)を使っています。イベントドリブンとはイベントが発生した時、それを処理するという仕組みでプログラムを動作させるプログラミング手法です。 Windows のアプリケーションソフトは、常に動き続けるように書いてはいけません。 Windows が必要に応じて送ってくる「イベント」を処理しては終了するというプログラムを書き、イベントの管理は Windows に委ねます。イベントとは、例えばユーザは画面上のオブジェクトにマウスやキーボードを使ってメッセージを送りますが、これがイベントになります。この操作を受け取った Windows はイベントとしてアプリケーションに送ります。

また、Windows のプログラミングにおいて、 GUI がある程度共通の方が注ごうが良いです。そのため、Windows のソフトを作る際、ウィンドウのデザインは一から全て作るのではなく、ウィンドウのタイプ、メニュー、ボタンなどをパラメータで指定します。この指定のためのファイルはリソースファイルと呼ばれ、リソースコンパイラで別にコンパイルし、実際の処理を行うプログラムにリンクします。

このため、Windows のソフトは次の形になります。


#include <Windows.h>
int WINAPI WinMain(引数){
  リソースの指定と本当のアプリケーションの関数を登録;
  終了;
}
void 本当のアプリケーション(イベント)
{
  switch(イベント){
  case メッセージ1:{
    メッセージ1 が来た時の処理;
    終了;
  }
  case メッセージ2:{
    メッセージ2 が来た時の処理;
    終了;
  }
  ...
  }
}

Windows のイベントは UINT 型です。今回は次の 3 つのイベントの処理を説明します。

WM_INITDIALOG: 一番最初に呼び出される時に受けるイベント。ここでウィンドウを作ったり、変数を初期化したりする。
WM_PAINT: 画面を表示しなければならなくなった時(ウィンドウが開いたとか、上に乗っているウィンドウが無くなったとか)受けるイベント。ここに表示したい画面を書くプログラムを置く。
WM_COMMAND: ボタンを押されるなど、ユーザからの指示により発生するイベント。イベントの内容はさらに引数で与えられる。特に、 IDCANCEL はウィンドウの閉じるボタン(X)で発生するイベントであり、アプリケーションの終了操作を行わねばならない。

さて、前節で説明したタートルグラフィックを Windows で実現するには、今説明した Windows のプログラミングに従い、その上で Turtle クラスを結合します。そして、実際にグラフィックを表示させる部分は WM_PAINT イベントの処理で書きます。なお、Windows ではウィンドウやグラフィックの対象などいろいろな資源がハンドルと呼ばれる一種の変数により参照されます。また、現在の点という概念がタートルグラフィックとは別に存在しており、 MoveToEX という現在点を移動させる関数と LineTo という新しい点まで線を引く関数が用意されています。以下に四角を画面に表示するプログラムを示します。HWND や POINT などは Windows で管理しなければならないウィンドウや点を示します。


//turtle.h
#include <Windows.h>
class Turtle {
private:
  HWND hwnd;
  PAINTSTRUCT ps;
  POINT sp;
  double x,y;
  double angle;
public:
  Turtle(HWND);
  ~Turtle();
  void forward(double);
  void turn(double);
  void home(int,int);
  void skip(double);
};


//turtle.cpp
#include <Windows.h>
#include <cmath>
#include "turtle.h"
Turtle::Turtle(HWND h){
  hwnd=h;
  BeginPaint(hwnd, &ps);
}
Turtle::~Turtle(){
  EndPaint(hwnd, &ps);
}
void Turtle::forward(double n){
  double dx,dy;
  dx=n*std::cos(angle);
  dy=n*std::sin(angle);
  LineTo(ps.hdc,static_cast<int>(x+=dx),static_cast<int>(y+=dy));
}
void Turtle::turn(double dangle){
  angle += dangle * 3.141592 / 180;
}
void Turtle::home(int _x, int _y){
  x=static_cast<double>(_x);
  y=static_cast<ouble>(_y);
  angle=0.0;
  MoveToEx(ps.hdc, _x, _y, &sp);
}
void Turtle::skip(double n){
  double dx,dy;
  dx=n*std::cos(angle);
  dy=n*std::sin(angle);
  MoveToEx(ps.hdc, static_cast<int>(x+=dx), static_cast<int>(y+=dy), &sp);
}


//box.h
#define XSIZE 100
#define YSIZE 100


//box.cpp
#include <Windows.h>
#include "box.h"
#include "turtle.h"

BOOL CALLBACK box( HWND, UINT, WPARAM, LPARAM );
int x_size, y_size;

int WINAPI WinMain( HINSTANCE hInstance, HINSTANCE, LPSTR, int)
{
  DialogBox( hInstance, "DLG_DATA", HWND_DESKTOP, (DLGPROC)box ) ;
  return 0;
}

BOOL CALLBACK box( HWND hwnd, UINT msg, WPARAM wp, LPARAM lp)
{
  static HWND hwnd_gr;

  switch(msg){
  case WM_INITDIALOG:{
    HDC hdc = GetDC(hwnd);
    TEXTMETRIC tm;
    GetTextMetrics(hdc, &tm);
    ReleaseDC(hwnd, hdc);
    y_size = static_cast<int>(
    static_cast<double>(YSIZE)/8.0*tm.tmHeight);
    x_size = static_cast<int>(
    static_cast<double>(XSIZE)/4.0*tm.tmAveCharWidth);
    return TRUE;
  }
  case WM_PAINT:{
    Turtle t(hwnd);
    t.home(x_size/2,y_size/2);
    t.forward(10);
    t.turn(90);
    t.forward(10);
    t.turn(90);
    t.forward(10);
    t.turn(90);
    t.forward(10);
    return TRUE;
  }
  case WM_COMMAND:
    switch(LOWORD(wp)){
    case IDCANCEL:
      EndDialog( hwnd, -1);
      return TRUE;
    }
  }
  return FALSE;
}


//box.rc
#include <windows.h>
#include "box.h"

DLG_DATA DIALOG DISCARDABLE 10, 10, XSIZE, YSIZE
STYLE DS_MODALFRAME | WS_POPUP | WS_VISIBLE | WS_CAPTION | WS_SYSMENU
CAPTION "Box"
FONT 10, "system"
BEGIN
END


# Makefile
TARGET = box
CXX = g++
RESC = windres
RES_INCS = 
LIBS = -lgdi32
.SUFFIXES: .ro .rc
.rc.ro:
	$(RESC) $(RES_INCS) -i $< -o $@ -O coff

$(TARGET).exe: $(TARGET).o $(TARGET).ro turtle.o
	$(CXX) -o $@ $^ $(LIBS)

turtle.o: turtle.h
$(TARGET).ro: $(TARGET).h
$(TARGET).o: $(TARGET).h

なおターゲットファイル一つだけの名前を取り出すために $< という変数を使用しています。これにより box.rc を参照でき、正しくリソースファイルを作ることが出来ます。

4-5. 再帰処理によるグラフィック

このタートルグラフィックと再帰処理を用いてグラフィックを描きましょう。木のような図形を考えます。幹を一本描き、その先から短い幹が左右に出るような図形を考えます。この図形を描く関数を tree(int length) とします。するとこの関数は次のような手順で描けます。

length 分だけ幹を描きます。
左に曲がり、 tree(length / ○) を描く。
同じ場所で右に曲がり、 tree(length / ○) を描く。

ここで、左右にそれぞれ 30 度曲がることにします。また、長さは毎回 1/2 になることにします。そして、上の手順にあるように左右で同じ地点から出発しなければなりませんので tree の手続きが終ったら元の位置に戻ることにします。この時向きは始めの向きから 180 度曲がった方向を向いているものとします。まとめると次のようになります。

length が 1 より小さければ 180 度回転して終了する。
length 分だけ幹を描きます。
左に 30 度曲がり、 tree(length / 2) を描く。
左に 120 度曲がり、 tree(length / 2) を描く。
左に 30 度曲がり、 length 分だけ進みます。


void tree(Turtle &t, int length){
  if(length < 1){
    t.turn(180);
    return;
  }
  t.forward(length);
  t.turn(30); tree(t, length/2);
  t.turn(120); tree(t, length/2);
  t.turn(30); t.skip(length);
  return;
}

演習4-6

上の tree を完成させなさい。

演習4-7

Koch 曲線とは次のような曲線です。この曲線を描きなさい。

1 次の Koch 曲線は長さ s の直線です。
n 次の Koch 曲線は次の 4 つの部分に分かれます。

長さ s/3 の n-1 次の Koch 曲線
左に 60 度曲がった後、長さ s/3 の n-1 次の Koch 曲線
右に 120 度曲がった後、長さ s/3 の n-1 次の Koch 曲線
左に 60 度曲がった後、長さ s/3 の n-1 次の Koch 曲線

4-6. Java での再帰グラフィック

Java ではグラフィックを扱うのに AWT と Swing の二種類の方法があります。 AWT は古い実装で機種に依存していましたが、 Swing は機種に依存しないグラフィックインターフェースライブラリを実現しています。したがって、ここでは Swing を使うことにします。ここで、上に示した C++ のタートルグラフィックと同等の機能を実現するためのサンプルを以下に示します。


import java.awt.*;
import java.awt.geom.*;
import javax.swing.*;
class Test {
    public static void main(String[] args){
	DrawFrame frame = new DrawFrame();
	frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
	frame.setVisible(true);
    }
}
class DrawFrame extends JFrame {
    public DrawFrame(){
	setTitle("Turtle Graphics");
	setSize(WIDTH, HEIGHT);
	DrawPanel panel = new DrawPanel();
	Container contentPane = getContentPane();
	contentPane.add(panel);
    }
    public static final int WIDTH = 100;
    public static final int HEIGHT = 200;
}
class DrawPanel extends JPanel {
    public void paintComponent(Graphics g){
	super.paintComponent(g);
	Turtle t = new Turtle((Graphics2D) g);
	t.forward(10);
	t.turn(90);
	t.forward(10);
	t.turn(90);
	t.forward(10);
	t.turn(90);
	t.forward(10);	
    }
}
class Turtle {
    double x,y,angle;
    Graphics2D g;
    Turtle(Graphics2D _g){
	x=(double)DrawFrame.WIDTH/2;
	y=(double)DrawFrame.HEIGHT/2;
	angle=0;
	g=_g;
    }
    public void home(double _x, double _y){
	x=_x;
	y=_y;
	angle=0;
    }
    public void forward(double n){
	double dx=n*Math.cos(angle);
	double dy=n*Math.sin(angle);
	g.draw(new Line2D.Double(x,y,x+dx,y+dy));
	x+=dx;
	y+=dy;
    }
    public void turn(double d){
	angle+=d*Math.PI/180;
    }
    public void skip(double n){
	double dx= n*Math.cos(angle);
	double dy= n*Math.sin(angle);
	x+=dx;
	y+=dy;
    }
}

このように Swing では一番外側の Window はフレームと呼ばれ、 JFrame のサブクラスのインスタンスとして生成されます。そして、フレームの構成要素である contentPain と呼ばれる描画領域に部品を貼り付けることで描画します。ここでは Graphics オブジェクト一つだけ貼り付け、 Graphic オブジェクトに Line2D オブジェクトを送ることで線を描きます。

坂本直志 <sakamoto@c.dendai.ac.jp>
東京電機大学工学部情報通信工学科

第 4 回 再帰処理