①最大公約数を求める直接再帰の例【ユークリッドの互除法】
※ユークリッドの互除法での問題
長方形を正方形で埋め尽くす。
そのようにして作ることのできる正方形の最大の辺の長さを求めよ。
#include <stdio.h>
int gcd(int x,int y){
if(y==0) return x;
else return gcd(y,x%y);
}
int main() {
int x,y;
printf("二つの整数の最大公約数を求める。");
printf("1つ目の値を入力せよ:");
scanf("%d",&x);
printf("2つ目の値を入力せよ:");
scanf("%d",&y);
printf("最大公約数は、%dです。¥n",gcd(x,y));
return 0;
}
※gcd=(greatest common divisor:最大公約数)
②正の整数の階乗を求める直接再帰の例
#include <stdio.h>
int factorial(int n){
if(n>0) return
n*factrial(n-1);
else return 1;
}
int main(){
int x;
printf("整数を入力せよ:");
scanf("%d",&x);
printf("%dの階乗は、%dです。¥n",x,factorial(x));
return 0;
}
③ハノイの塔問題を直接再帰で求める構文例
#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 main(){
int n;
printf("ハノイの塔¥n円盤の枚数:");
scanf("%d",&n);
move(n,1,3);
return 0;
}
参考文献:明解 C言語によるアルゴリズムとデータ構造