再帰処理を使用して配列内の数値を整列させる_1（再帰、クイックソート）
gifu_shino.gこのページでは、再帰処理を簡単に説明してみます。
再帰処理ですが、ある関数が自分自身を複数回呼び出し、
処理を進めるものをいいます。
// メイン関数
main( ){
func( );
}
// 再帰するように記述した関数
func( ){
func( )
}
この２つの関数からなるプログラムは、
1.メイン関数が実行されることで処理が開始されます。
2.メイン関が、再帰するように記述した関数func( )を
を飛び出します。
3.func( )関数が実行され、自関数 func( )関数が
再び呼び出されます。
4.3.の処理が無限に繰り返されます。
このような流れで、処理を進めるものです。
ですが、この例では、再帰を中断する仕組みが記述されて
いないので無限ループとなり、いずれメモリが消費され、
ハングアップします。
もう少し記述のあるものを図にしてみます。
このプログラムでは、
fanc( )関数を呼び出し時に引数で与えられた値が、
1より大きい場合、その値から１減算して、再び
fanc( )関数を呼び出すものです。
引数で与えられた値が、1になった時点で、再帰処理が
行われず、呼び出しを行ったfanc( )関数に処理が戻り、
呼び出しとは逆順に辿り、最後に最初fanc( )関数を呼び出した、
メイン関数へと戻り処理が終了します。
※この時、イメージとしてメモリ上には、メイン関数と、
再帰処理された数のfanc( )関数が積み上げられている
ことになります。この図の場合、メイン関数と、
fanc( )関数4つが一時的に常駐することになります。
実際の使用例として、
"1～10までの整数値の加算結果を表示する" プログラムを、
・繰り返し制御文 for( )文
関数名：fanc_repetition( )
・再帰処理
関数名：fanc_recursion
の二つの処理方法で記述し、比較してみます。
・プロジェクトを作成します。
Visual Studio 2022を起動し、
新しいプロジェクトを作成します。
・プロジェクトタイプ："コンソールアプリ"
・プロジェクト名："ct_108_1"
とします。
・プログラム記述・編集画面が表示されるので、
以下のプログラムを記述します。
プログラムの記述内容
// 繰り返し制御文と再帰処理
#include <iostream>
// プロトタイプ宣言
// 再帰処理による整数加算関数
int fanc_recursion(int);
// 繰り返し制御文による整数加算関数
int fanc_repetition(int);
// メイン関数
int main()
{
// 変数宣言
int ret;
// 再帰処理関数による 1～引数 までの整数加算関数呼び出し
ret = fanc_recursion(10);
// 計算結果表示
printf("再帰：%d\n", ret);
// 繰り返し制御文関数による 1～引数 までの整数加算関数呼び出し
ret = fanc_repetition(10);
// 計算結果表示
printf("繰り返し：%d\n", ret);
return EXIT_SUCCESS;
}
// 再帰処理による整数加算関数
int fanc_recursion(int x) {
if (x > 1) {
x = x + fanc_recursion(x - 1);
return x;
}
}
// 繰り返し制御文による整数加算関数
int fanc_repetition(int x) {
for (int i = x - 1; i > 0; i--) {
x += i;
}
return x;
}
※実際のプログラム例では、10, 9, 8・・・1 と
引数より1ずつ減算しながらの加算となっています。
・実行結果は、もちろんですが、両関数とも同じ結果 55 です。
もう１つ、
再帰処理による、階乗計算の結果を求めるプログラムを
記述してみます。
階乗計算は、指定された値以下の数値を掛け合わせた結果を
求めるもので、この指定数値は、キーボードから入力
するものとします。
※この時の数値とは自然数です。
指定数が 5 の場合、5 × 4 × 3 × 2 × 1 です。
・プロジェクトを作成します。
Visual Studio 2022を起動し、
新しいプロジェクトを作成します。
・プロジェクトタイプ："コンソールアプリ"
・プロジェクト名："ct_108_2"
とします。
プログラムの記述内容
// 再帰処理による階乗計算
#include <iostream>
// プロトタイプ宣言
int factorial_fanc(int);
// メイン関数
int main()
{
// 変数宣言
int result;
int value;
// キーボードからの値を受け取る
printf("階乗を求める数値：");
scanf_s("%d", &value);
// 階乗関数呼び出し
result = factorial_fanc(value);
// 計算結果の表示
printf("%dの階乗計算結果：%d\n", value, result);
return EXIT_SUCCESS;
}
// 階乗を求める関数
int factorial_fanc(int val) {
if (val < 1) {
return 1;
}
return (val * factorial_fanc(val - 1));
}
・実行結果は、キーボードから整数値 4 を入力した時の例です。
4 × 3 × 2 × 1 の結果となり、結果は 24 となります。
