階乗値を求めるプログラム 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
