再起呼び出し

階乗値を求めるプログラム factorial.c

#include <stdio.h>

int factorial(int n) 
{
	if (n > 0)
		return n * factorial(n - 1);
	else 
		return 1;
}

int main(void)
{
	int x;

	printf("整数を入力せよ：");
	scanf_s("%d", &x);
	printf("%dの階乗は%dです。\n", x, factorial(x));
	return 0;
}

最大公約数を求めるプログラム euclid.c

#include <stdio.h>

int gcd(int x, int y) 
{
	if (y == 0)
		return x;
	else
		return gcd(y, x % y);
}

int main(void)
{
	int x, y;
	puts("二つの整数の最大公約数を求めます。");
	printf("整数を入力せよ:");
	scanf_s("%d", &x);
	printf("整数を入力せよ:");
	scanf_s("%d", &y);
	printf("最大公約数は%dです。\n", gcd(x, y));
	return 0;
}

ひとつのプロジェクト内に複数のmain関数を作るとエラーになる。

複数の機能を扱いたい場合は、前にリストやハッシュで作ったものと同様に、メニューを作って呼び分けるようにする。

RecursiveTest.c

#include <stdio.h>
#include "recursive.h"

typedef enum {
	TERMINATE, FACTORIAL, EUCLID
} Menu;

Menu SelectMenu(void)
{
	int ch;
	do {
		printf("(1)階乗 (2)最大公約数 (0)終了");
		scanf_s("%d", &ch);
	} while (ch < TERMINATE || ch > EUCLID);
	return (Menu)ch;
}

int main(void)
{
	Menu menu;
	do {
		switch (menu = SelectMenu()) {
		case FACTORIAL:
			fmain();
			break;
		case EUCLID:
			emain();
			break;
		}
	} while (menu != TERMINATE);
	return 0;
}

recursive.h

#ifndef __RECURSIVE
#define __RECURSIVE

int fmain(void);
int emain(void);

#endif

factorial.c の main() を fmain() に変更し、euclid.c の main() を emain() に変更する。

テキストの演習問題をやってみよう！

ネットで検索してもOK！
ただし、動作をきちんと自分で理解すること。

演習5-1
再帰関数呼び出しを用いずに、関数factorialを実現せよ。

演習5-2
再帰関数呼び出しを用いずに、関数euclidを実現せよ。

作成済みの再帰呼び出し関数は、関数名の最後に _r をつけてエラー回避する。
factorial() → factorial_r()
euclid() → euclid_r()

演習5-1解答例

int factorial(int n)
{
	int i;
	int result = 1;
	for (i = 1; i <= n; i++) {
		result = result * i;
	}
	return result;
}

演習5-2解答例

int gcd(int x, int y)
{
	int v = (x < y) ? x : y;
	int i;

	for (i = v; i > 0; i--) {
		//printf("x=%d y=%d v=%d xv=%d yv=%d\n", x, y, i, x % i, y % i);
		if ((x % i == 0) && (y % i == 0)) {
			return i;
		}
	}
	return 1;
}

再帰アルゴリズムの解析
RecursiveTest.cに追加

#include <stdio.h>
#include "recursive.h"

typedef enum {
	TERMINATE, FACTORIAL, EUCLID, ANALYZE
} Menu;

Menu SelectMenu(void)
{
	int ch;
	do {
		printf("(1)階乗 (2)最大公約数 (3)解析 (0)終了 : ");
		scanf_s("%d", &ch);
	} while (ch < TERMINATE || ch > ANALYZE);
	return (Menu)ch;
}

int main(void)
{
	Menu menu;
	do {
		switch (menu = SelectMenu()) {
		case FACTORIAL:
			fmain();
			break;
		case EUCLID:
			emain();
			break;
		case ANALYZE:
			amain();
			break;
		}
	} while (menu != TERMINATE);
	return 0;
}

recur.c

#include <stdio.h>

void recur(int n)
{
	if (n > 0) {
		recur(n - 1);
		printf("%d\n", n);
		recur(n - 2);
	}
}

int amain(void)
{
	int x;
	printf("整数を入力せよ: ");
	scanf("%d", &x);
	recur(x);
	return 0;
}

recursive.h

#ifndef __RECURSIVE
#define __RECURSIVE

int fmain(void);
int emain(void);
int amain(void);

#endif

ハノイの塔
hanoi.c

#include <stdio.h>

void move(int no, int x, int y) 
{
	if (no > 1)
		move(no - 1, x, 6 - x - y);
	printf("円盤[%d]を%d軸から%d軸へ移動\n", no, x, y);
	if (no > 1)
		move(no - 1, 6 - x - y, y);
}

int hmain(void) 
{
	int n;
	printf("ハノイの塔\n円盤の枚数: ");
	scanf("%d", &n);
	move(n, 1, 3);
	return 0;
}

RecursiveTest.c

#include <stdio.h>
#include "recursive.h"

typedef enum {
	TERMINATE, FACTORIAL, EUCLID, ANALYZE, HANOI
} Menu;

Menu SelectMenu(void)
{
	int ch;
	do {
		printf("(1)階乗 (2)最大公約数 (3)解析 (4)ハノイの塔 (0)終了 : ");
		scanf_s("%d", &ch);
	} while (ch < TERMINATE || ch > HANOI);
	return (Menu)ch;
}

int main(void)
{
	Menu menu;
	do {
		switch (menu = SelectMenu()) {
		case FACTORIAL:
			fmain();
			break;
		case EUCLID:
			emain();
			break;
		case ANALYZE:
			amain();
			break;
		case HANOI:
			hmain();
			break;
		}
	} while (menu != TERMINATE);
	return 0;
}

recursive.h

#ifndef __RECURSIVE
#define __RECURSIVE

int fmain(void);
int emain(void);
int amain(void);
int hmain(void);

#endif