C 言語 | 関数 | 再帰処理

Tags:

自分自身を呼び出す関数による再帰処理について説明する。

自分自身を呼び出す関数

これまで、ある関数から別の関数を呼び出す方法を説明した。それでは、関数の中で自分自身を呼び出すとどうなるだろうか。関数内で自分自身を呼び出すことを再帰と呼ぶ。たとえば、次の関数を考えてみよう。

void Function() {
 Function();
}

Function() 関数は、関数内で自分自身を呼び出している。この場合は自分自身を永遠に呼び出すため、無限ループに陥る。

再帰を使うと特殊なループを作成できる。しかし、その多くは再帰を使わなくても反復文で実現できる。関数呼び出しは反復文によるループよりも遅いため、再帰を使う場面は限られている。一方で、一部のアルゴリズムを単純化できる利点がある。

コード 1

#include <stdio.h>

void Function(int , int);

int main() {
 Function(0 , 10);
 return 0;
}

void Function(int iCount , int iMax) {
  if (iCount < iMax) {
    printf("Count = %d\n" , iCount);
   Function(iCount + 1 , iMax);
  }
}

コード 1 は、再帰処理の使い方を理解するための簡単なプログラムである。再帰処理を行う Function() 関数は、第 1 引数にカウンターの初期値、第 2 引数に最大値を受け取る。iCount が iMax より小さい間は、Function(iCount + 1, iMax) のようにカウンターを増やして自分自身を呼び出す。

この処理を繰り返すと、iCount はやがて iMax に到達する。その後、各 Function() 関数は逆順に制御を返し、最後に最初の呼び出し元へ戻る。このほか、関数 A() が関数 B() を呼び出し、関数 B() が関数 A() を呼び出す相互再帰もある。

void FunctionA() {
 FunctionB();
}

void FunctionB() {
 FunctionA();
}

再帰を実際に使う場面は多くないが、ツリー構造のようなデータの解析や検索などに応用される。