関数２（再帰）

関数を再帰的に定義すると， 繰り返しの複雑な処理を簡単に記述できることがよくある．

教科書の該当範囲：なし

基礎知識

関数の再帰的定義では， その関数を作るために， その関数自身を利用する： 

// 関数の再帰的定義の基本パターン
... func(...)
{
	...
	if (...) return (...);	// 終了条件
	...
	func(...);		// 再帰呼び出し
	...
	return (...);
}

再帰呼び出しによって， その関数自身の先頭へ戻るようなループを形成している． メイン関数などからこの関数を呼び出すと， この関数内の処理が繰り返し実行されることになる．

必ず，終了条件によって， 繰り返しを終了すること． または，継続条件によって， 再帰呼び出しするのでもよい．

反復と再帰

数学

自然数の 1 から n までの総和 Sn を例として， 反復的な計算を再帰的に定義し直してみよう．

プログラミングの前に，まずは数式として定義しておこう：

プログラミング

次にＣ言語の関数として定義してみよう． ソース sum.c： 

#include <stdio.h>

// 自然数 1 から n までの総和を計算する関数の反復版
int sum1(int n)
{
	int	i;
	int	s = 0;

	for (i = 1; i <= n; i++) {	// i = 1, 2, 3, ..., n
		s += i;			// S_i = ((...) + i)
	}
	return (s);			// S_n
}

// 自然数 1 から n までの総和を計算する関数の再帰版
int sum2(int n)
{
	if (n == 0) return (0);		// S_n = 0
	return (sum2(n - 1) + n);	// S_n = S_n-1 + n
}

int main(void)
{
	int	n;

	printf("自然数 n > ");
	scanf("%d", &n);
	printf("反復版... 総和 = %d\n", sum1(n));
	printf("再帰版... 総和 = %d\n", sum2(n));
	return (0);
}

総和関数として反復版 sum1() と再帰版 sum2() の２つが定義されているが， 実行結果は当然，どちらも同じとなる．

しかし，ソースコードはかなり異なり． 再帰版では，同じ計算のコードを実にコンパクトに表現できている． 反復版では，カウンタや結果記憶のために必要な変数が コードサイズ増加の原因となっている．

まぁ，元々の問題が簡単なので， 反復版の方のコードもそれなりに簡単ですが， 再帰版のコードはそれ以上に簡単．
再帰版 sum() の動作説明図
注意事項

「反復」と「再帰」は，結果としては同じように見えるが， 方法としては異なる．混同しないこと!! 問題に応じて相応しい方法を採用しよう．

なお，反復では無限回の繰り返しも可能であったが， 再帰では有限回までしか実行できない． したがって，再帰では特に終了条件が重要となるが， 書き忘れやすいので注意しよう．

なぜ無限には再帰できないのか？ 再帰呼び出しは，実際には，関数自身を直接呼び出してはおらず， プログラムの内部的には，関数の分身を作り，分身の方を呼び出している． このとき，関数内のデータ（変数，引数，戻り値）をコピーするため メモリ領域を消費する． 利用可能なメモリ領域の限界以上に再帰しようとすると， スタックオーバフロー（stack overflow）となり， プログラムは強制終了されてしまう．

分身を作らないと，return でどこに戻れば？ 戻った後，変数の元の値は何だった？ とかの不都合があるので，仕方ない．

反復と再帰の使い分け基準：

例：再帰によるカウント

カウントアップ／ダウンの処理を再帰的に定義してみよう． （本来は，for 文での反復の方が相応しい処理ではあるが， 再帰の理解を深めるため強引に...）

ソース count.c： 

#include <stdio.h>

/*
カウントアップ表示する関数の再帰版
引数 n：最終値（初期値はゼロ）
戻り値：なし
*/
void countup(int n)
{
	if (n > 0) countup(n - 1);	// 0〜(n-1)を表示
	printf("%d\n", n);		// nを表示
}

/*
カウントダウン表示する関数の再帰版
引数 n：初期値（最終値はゼロ）
戻り値：なし
*/
void countdown(int n)
{
	printf("%d\n", n);		// nを表示
	if (n > 0) countdown(n - 1);	// (n-1)〜0を表示
}

int main(void)
{
	int	n;

	printf("自然数 n > ");
	scanf("%d", &n);

	printf("カウントアップ：\n");
	countup(n);

	printf("カウントダウン：\n");
	countdown(n);

	return (0);
}

この例では，繰り返しの終了が終了条件ではなく継続条件として記述されている． 終了条件として書いてもよいが，コードが少し長くなってしまう： 

void countup(int n)
{
	if (n < 0) return;
	countup(n - 1);
	printf("%d\n", n);
}

本日の課題

  1. 前回の例題の 累乗関数 int power(int x, int y) の再帰版を定義せよ． なお，テスト用メイン関数も定義し， ソースファイルを power.c とすること．

    2. ヒント：（定義式） 

    xy ＝ x x x ... x

y ＝ 0 に対して xy ＝ 1
y ＞ 0 に対して xy ＝ xy − 1 x
  2. 前回の課題の 階乗関数 int factorial(int n) の再帰版を定義せよ． なお，テスト用メイン関数も定義し， ソースファイルを factorial.c とすること．

    3. ヒント：（定義式） 

    n! ＝ 1 × 2 × 3 × ... × n

n ＝ 0 に対して n! ＝ 1				// 要するに f(n) として 1 を返す
n ＞ 0 に対して n! ＝ (n − 1)! n		// f(n) として f(n-1) * n を返す

余裕ある人は，過去に作成した mul.c，div.c， 等を再帰的に関数化してみては？

提出：

(c) 2018, yanagawa@kushiro-ct.ac.jp