当日のOHP資料です。
関数の再帰的定義( Text p.194 - 197 )
-->
Download : sample-001.c ( SJIS 版 )
/*
* 再帰的関数の例 factrial
*/
#include <stdio.h>
/*
* 階乗 (factrial) の再帰的定義
*
* n * f(n-1) ( n > 0 )
* f(n) = {
* 1 ( other )
*/
int factrial ( int n ) {
if ( n > 0 ) {
return n * factrial ( n - 1 ); // factrial 関数の定義の中で factrial を利用
} else {
return 1;
}
}
/*
* main
*/
int main ( void ) {
int nat; // 自然数
printf ( "小さな自然数を入力してください : " );
scanf ( "%d", &nat );
printf ( "%d の階乗は %d です。\n", nat, factrial ( nat ) );
return 0;
}
5
C:\usr\c\> sample-001 小さな自然数を入力してください : 5 5 の階乗は 120 です。 C:\usr\c\>
Download : sample-002.c ( SJIS 版 )
/*
* 再帰を利用しない関数定義の例
*/
#include <stdio.h>
/*
*
*/
void funcAAA() {
printf ( "\t\t\tAAA\n" );
}
/*
*
*/
void funcAAB() {
printf ( "\t\t\tAAB\n" );
}
/*
*
*/
void funcAA() {
printf ( "\t\tAA\n" );
funcAAA();
funcAAB();
}
/*
*
*/
void funcABA() {
printf ( "\t\t\tABA\n" );
}
/*
*
*/
void funcABB() {
printf ( "\t\t\tABB\n" );
}
/*
*
*/
void funcAB() {
printf ( "\t\tAB\n" );
funcABA();
funcABB();
}
/*
*
*/
void funcA() {
printf ( "\tA\n" );
funcAA();
funcAB();
}
/*
*
*/
void funcBAA() {
printf ( "\t\t\tBAA\n" );
}
/*
*
*/
void funcBAB() {
printf ( "\t\t\tBAB\n" );
}
/*
*
*/
void funcBA() {
printf ( "\t\tBA\n" );
funcBAA();
funcBAB();
}
/*
*
*/
void funcBBA() {
printf ( "\t\t\tBBA\n" );
}
/*
*
*/
void funcBBB() {
printf ( "\t\t\tBBB\n" );
}
/*
*
*/
void funcBB() {
printf ( "\t\tBB\n" );
funcBBA();
funcBBB();
}
/*
*
*/
void funcB() {
printf ( "\tB\n" );
funcBA();
funcBB();
}
/*
* main
*/
int main ( void ) {
printf ( "main\n" );
funcA();
funcB();
return 0;
}
C:\usr\c\> sample-002 main A AA AAA AAB AB ABA ABB B BA BAA BAB BB BBA BBB C:\usr\c\>
Download : sample-003.c ( SJIS 版 )
/*
* 全ての自然数は偶数か奇数
*/
#include <stdio.h>
/*
* EVEN ( n = 0 )
* parity ( n ) { ODD ( parity ( n - 1 ) = EVEN )
* EVEN ( parity ( n - 1 ) = ODD )
*/
#define EVEN 0
#define ODD 1
int parity ( int n ) {
if ( n == 0 ) {
return EVEN;
} else if ( parity ( n - 1 ) == EVEN ) {
return ODD;
} else {
return EVEN;
}
}
/*
* main
*/
int main ( void ) {
int nat; // 自然数
printf ( "小さな自然数を入力してください : " );
scanf ( "%d", &nat );
if ( parity ( nat ) == EVEN ) {
printf ( "%d は偶数です\n", nat );
} else {
printf ( "%d は奇数です\n", nat );
}
return 0;
}
5
C:\usr\c\> sample-003 小さな自然数を入力してください : 5 5 は奇数です C:\usr\c\>
Download : sample-004.c ( SJIS 版 )
/*
* 配列の要素の総和を計算する再帰的な関数
*/
#include <stdio.h>
/*
* sum ( array, size-1 ) + array[size-1] ( size > 0 )
* sum ( array, size ) = {
* 0 ( othewise )
*/
int sum ( int array[], int size ) {
if ( size > 0 ) {
return sum ( array, size - 1 ) + array [ size - 1 ];
} else {
return 0;
}
}
/*
* main
*/
#define ARRAY_SIZE 5
int main ( void ) {
int numbers[ARRAY_SIZE]; // ARRAY_SIZE 個の整数値を保存する配列
int index; // 何番目の整数か
printf ( "%d 個の整数値を入力し、その逆順に出力します。\n", ARRAY_SIZE );
for ( index = 0; index < ARRAY_SIZE; index++ ) {
printf ( "%2d 番目の数値を入力してください : ", index + 1 );
scanf ( "%d", &numbers[index] ); // index 番目の数値の入力
}
printf ( "これらの数の総和は %d です。\n", sum ( numbers, ARRAY_SIZE ) );
return 0;
}
47304 3 2957 602 73
C:\usr\c\> sample-004 5 個の整数値を入力し、その逆順に出力します。 1 番目の数値を入力してください : 47304 2 番目の数値を入力してください : 3 3 番目の数値を入力してください : 2957 4 番目の数値を入力してください : 602 5 番目の数値を入力してください : 73 これらの数の総和は 50939 です。 C:\usr\c\>
Download : sample-005.c ( SJIS 版 )
/*
* 再帰による自然数の判定
*/
#include <stdio.h>
/*
* n が 0 なら自然数
* isNat ( n ) {
* n - 1 が自然数なら n も自然数
*/
#define NO 0
#define YES (!NO)
int isNat ( int n ) {
if ( n == 0 ) {
return YES;
} else {
return isNat ( n - 1 );
}
/*
* n に負の数を入力すると、無限ループになる事に注意しよう
*/
}
/*
* main
*/
int main ( void ) {
int nat;
printf ( "自然数を入力してください : " );
scanf ( "%d", &nat );
if ( isNat ( nat ) == YES ) {
printf ( "%d は自然数です\n", nat );
} else {
printf ( "%d は自然数ではありません\n", nat );
/* 実際には、ここに来る事はない */
}
return 0;
}
6
C:\usr\c\> sample-005 自然数を入力してください : 6 6 は自然数です C:\usr\c\>
Download : sample-006.c ( SJIS 版 )
/*
* 再帰を利用した自然数上の計算
*/
#include <stdio.h>
/*
* succ n = n' = n + 1
*/
int succ ( int n ) {
return n + 1;
}
/*
* n ( m = 0 )
* add ( n, m ) = {
* succ ( add ( n, m - 1 ) ) ( otherwise )
*/
int add ( int n, int m ) {
if ( m == 0 ) {
return n;
} else {
return succ ( add ( n, m - 1 ) );
}
}
/*
* 0 ( m = 0 )
* mul ( n, m ) = {
* add ( mul ( n, m - 1 ), n ) ( otherwise )
*/
int mul ( int n, int m ) {
if ( m == 0 ) {
return 0;
} else {
return add ( mul ( n, m - 1 ), n );
}
}
/*
* 1 ( m = 0 )
* power ( n, m ) = {
* mul ( power ( n, m - 1 ), n ) ( otherwise )
*/
int power ( int n, int m ) {
if ( m == 0 ) {
return 1;
} else {
return mul ( power ( n, m - 1 ), n );
}
}
/*
* main
*/
int main ( void ) {
int base;
int exponent;
printf ( "底を入力してください : " );
scanf ( "%d", &base );
printf ( "指数を入力してください : " );
scanf ( "%d", &exponent );
printf ( "%d の %d は %d です。\n", base, exponent, power ( base, exponent ) );
return 0;
}
6 3
C:\usr\c\> sample-006 底を入力してください : 6 指数を入力してください : 3 6 の 3 は 216 です。 C:\usr\c\>
Download : sample-007.c ( SJIS 版 )
/*
* 配列の要素を再帰的に処理する関数
*/
#include <stdio.h>
/*
* scanf ( array[size-1] ); input ( array, size-1 ) ( size > 0 )
* input ( array, size ) = {
* -- ( othewise )
*/
void input ( int array[], int size ) {
if ( size > 0 ) {
printf ( "数を入力してください : " );
scanf ( "%d", &array[ size - 1 ] );
input ( array, size - 1 );
}
}
/*
* sum ( array, size-1 ) + array[size-1] ( size > 0 )
* sum ( array, size ) = {
* 0 ( othewise )
*/
int sum ( int array[], int size ) {
if ( size > 0 ) {
return sum ( array, size - 1 ) + array [ size - 1 ];
} else {
return 0;
}
}
/*
* print ( array, size-1 ) ; print ( array[size-1] ) ( size > 0 )
* print ( array, size ) = {
* -- ( othewise )
*/
void print ( int array[], int size ) {
if ( size > 0 ) {
printf ( "%d\n", array [ size - 1 ] );
print ( array, size - 1 );
}
}
/*
* main
*/
#define ARRAY_SIZE 5
int main ( void ) {
int numbers[ARRAY_SIZE]; // ARRAY_SIZE 個の整数値を保存する配列
input ( numbers, ARRAY_SIZE );
print ( numbers, ARRAY_SIZE );
printf ( "総和は %d です\n", sum ( numbers, ARRAY_SIZE ) );
return 0;
}
47304 3 2957 602 73
C:\usr\c\> sample-007 数を入力してください : 47304 数を入力してください : 3 数を入力してください : 2957 数を入力してください : 602 数を入力してください : 73 47304 3 2957 602 73 総和は 50939 です C:\usr\c\>
Download : sample-008.c ( SJIS 版 )
/*
* 最大公約数を計算する
*/
#include <stdio.h>
/*
* n ( m = 0 )
* gcm ( n, m ) = {
* gcm ( m, n % m ) ( otherwise )
*/
int gcm ( int n, int m ) {
if ( m == 0 ) {
return n;
} else {
return gcm ( m, n % m );
}
}
/*
* main
*/
int main ( void ) {
int n;
int m;
printf ( "一つ目の数を入力してください : " );
scanf ( "%d", &n );
printf ( "二つ目の数を入力してください : " );
scanf ( "%d", &m );
printf ( "%d と %d の最大公約数は %d です。\n", n, m, gcm ( n, m ) );
return 0;
}
12 18
C:\usr\c\> sample-008 一つ目の数を入力してください : 12 二つ目の数を入力してください : 18 12 と 18 の最大公約数は 6 です。 C:\usr\c\>
Download : sample-009.c ( SJIS 版 )
/*
* 再帰呼び出しと処理の順番 ( 前に処理 )
*/
#include <stdio.h>
/*
* recf 0 〜 n まで処理する
*/
void recf ( int n ) {
printf ( "recf ( %d )\n", n ); /* 再帰の前に処理をする */
if ( n > 0 ) {
recf ( n - 1 );
}
}
/*
* main
*/
int main ( void ) {
int nat;
printf ( "一つの数を入力してください : " );
scanf ( "%d", &nat );
recf ( nat );
return 0;
}
6
C:\usr\c\> sample-009 一つの数を入力してください : 6 recf ( 6 ) recf ( 5 ) recf ( 4 ) recf ( 3 ) recf ( 2 ) recf ( 1 ) recf ( 0 ) C:\usr\c\>
Download : sample-010.c ( SJIS 版 )
/*
* 再帰呼び出しと処理の順番 ( 後で処理 )
*/
#include <stdio.h>
/*
* recb 0 〜 n まで処理する
*/
void recb ( int n ) {
if ( n > 0 ) {
recb ( n - 1 );
}
printf ( "recb ( %d )\n", n ); /* 再帰の後で処理をする */
}
/*
* main
*/
int main ( void ) {
int nat;
printf ( "一つの数を入力してください : " );
scanf ( "%d", &nat );
recb ( nat );
return 0;
}
6
C:\usr\c\> sample-010 一つの数を入力してください : 6 recb ( 0 ) recb ( 1 ) recb ( 2 ) recb ( 3 ) recb ( 4 ) recb ( 5 ) recb ( 6 ) C:\usr\c\>
Download : sample-011.c ( SJIS 版 )
/*
* 再帰呼び出しと処理の順番 ( 前後で処理 )
*/
#include <stdio.h>
/*
* recfb 0 〜 n まで処理する
*/
void recfb ( int n ) {
printf ( "< recfb ( %d )\n", n ); /* 再帰の前に処理をする */
if ( n > 0 ) {
recfb ( n - 1 );
}
printf ( "> recfb ( %d )\n", n ); /* 再帰の後で処理をする */
}
/*
* main
*/
int main ( void ) {
int nat;
printf ( "一つの数を入力してください : " );
scanf ( "%d", &nat );
recfb ( nat );
return 0;
}
6
C:\usr\c\> sample-011 一つの数を入力してください : 6 < recfb ( 6 ) < recfb ( 5 ) < recfb ( 4 ) < recfb ( 3 ) < recfb ( 2 ) < recfb ( 1 ) < recfb ( 0 ) > recfb ( 0 ) > recfb ( 1 ) > recfb ( 2 ) > recfb ( 3 ) > recfb ( 4 ) > recfb ( 5 ) > recfb ( 6 ) C:\usr\c\>
Download : sample-012.c ( SJIS 版 )
/*
* 再帰呼び出しと処理の順番 ( 前から加える )
*/
#include <stdio.h>
/*
* 1 〜 1/n まで、前から加える
*/
float sumif ( int n ) {
if ( n > 0 ) {
return sumif ( n - 1 ) + ( 1/(float)n );
} else {
return 0.0;
}
}
/*
* main
*/
int main ( void ) {
int nat;
printf ( "一つの数を入力してください : " );
scanf ( "%d", &nat );
printf ( "1 〜 1/%d までの総和は %f です\n", nat, sumif ( nat ) );
return 0;
}
100000
C:\usr\c\> sample-012 一つの数を入力してください : 100000 1 〜 1/100000 までの総和は 12.090146 です C:\usr\c\>
Download : sample-013.c ( SJIS 版 )
/*
* 再帰呼び出しと処理の順番 ( 後から加える )
*/
#include <stdio.h>
/*
* 1 〜 1/n まで、後から加える
*/
float sumib0 ( int n, float sum ) {
if ( n > 0 ) {
return sumib0 ( n - 1, sum + ( 1/(float)n ) );
} else {
return sum;
}
}
float sumib ( int n ) {
return sumib0 ( n, 0.0 );
}
/*
* main
*/
int main ( void ) {
int nat;
printf ( "一つの数を入力してください : " );
scanf ( "%d", &nat );
printf ( "1 〜 1/%d までの総和は %f です\n", nat, sumib ( nat ) );
return 0;
}
100000
C:\usr\c\> sample-013 一つの数を入力してください : 100000 1 〜 1/100000 までの総和は 12.090152 です C:\usr\c\>
Download : sample-014.c ( SJIS 版 )
/*
* ハノイの塔の問題を解く手順
*/
#include <stdio.h>
/*
* ハノイの塔
*/
void hanoi ( int n, char from, char to, char work ) {
if ( n > 1 ) {
hanoi ( n - 1, from, work, to );
printf ( "%d の番号の円板を %c から %c に移動する\n", n, from, to );
hanoi ( n - 1, work, to, from );
} else {
printf ( "%d の番号の円板を %c から %c に移動する\n", n, from, to );
}
}
/*
* main
*/
int main ( void ) {
int hight;
printf ( "円板の枚数を入力してください : " );
scanf ( "%d", &hight );
printf ( "%d 枚の円板を A から C に移動する手順は以下のようになります。\n", hight );
hanoi ( hight, 'A', 'C', 'B' );
return 0;
}
3
C:\usr\c\> sample-014 円板の枚数を入力してください : 3 3 枚の円板を A から C に移動する手順は以下のようになります。 1 の番号の円板を A から C に移動する 2 の番号の円板を A から B に移動する 1 の番号の円板を C から B に移動する 3 の番号の円板を A から C に移動する 1 の番号の円板を B から A に移動する 2 の番号の円板を B から C に移動する 1 の番号の円板を A から C に移動する C:\usr\c\>
Download : sample-015.c ( SJIS 版 )
/*
* フィボナッチ数の計算
*/
#include <stdio.h>
/*
* フィボナッチ数
*/
int fibnacci ( int n ) {
if ( n > 1 ) {
return fibnacci ( n - 1 ) + fibnacci ( n - 2 );
} else {
return 1;
}
}
/*
* main
*/
int main ( void ) {
int nat;
printf ( "フィボナッチ数の何項目が欲しいですか ? : " );
scanf ( "%d", &nat );
printf ( "フィボナッチ数の第 %d 項は %d です。\n", nat, fibnacci ( nat ) );
return 0;
}
6
C:\usr\c\> sample-015 フィボナッチ数の何項目が欲しいですか ? : 6 フィボナッチ数の第 6 項は 13 です。 C:\usr\c\>