再帰（recursion）

• 関数は自分自身を直接あるいは間接に呼び出しても良い
• この様な呼出を再帰呼出（recursive call）という
• 帰納的に定義された関数の計算に使える
• 再帰的に定義されるデータ構造に便利

帰納的に定義された関数

　階乗（factorial）

• $1$から$n$までの自然数の積を$n$の階乗といい$n!$と書く
  $n!=1\times 2\times\cdots\times(n-1)\times n$
  $0!=1$と約束する
• 帰納的定義
  $f(0)=1\\f(n)=n\times f(n-1)\ \ (n\ge 1)$

#include <stdio.h>

int fact(int n)
{
	if( n == 0 )
		return( 1 );
	else
		return( n * fact(n-1) );
}

main()
{
	int	n;
	
	printf("Input a number: ");
	scanf("%d", &n );
	printf("%d! = %d\n", n, fact(n) );
}
/* end of fact.c */

• 負の数を入力してみよう

/* fact 改訂版 */
int fact(int n)
{
	if( n < 0 )
	{	/* 例外処理 */
		fprintf( stderr, "fact(n) error! n = %d < 0\n", n );
		exit(1);
		return( 0 ); /* dumy return */
	}
	else if( n == 0 )
		return( 1 );
	else
		return( n * fact(n-1) );
}

　フィボナッチ数列（Fibonacci sequence）

• 1，1よりはじめて順次に前の2項の和をつくることによって得られる数列
  1，1，2，3，5，8，13, ...
• 帰納的定義
  $f(1)=f(2)=1\\f(n)=f(n-1)+f(n-2)\ \ (n\ge 3)$

#include <stdio.h>

int fibo(int n)
{
	switch( n )
	{
	case 1:
	case 2:
		return( 1 );
	default:
		return( fibo(n-1) + fibo(n-2) );
	}
}

main()
{
	int	n;
	
	printf("Input a number: ");
	scanf("%d", &n );
	printf("fibo(%d) = %d\n", n, fibo(n) );
}
/* end of fibo.c */

• ０や負の数を入力してみよう

/* fibo 改訂版 */
int fibo(int n)
{
	if( n <= 0 )
	{	/* 例外処理 */
		fprintf( stderr, "fibo(n) error! n = %d <= 0\n", n );
		exit(1);
		return( 0 ); /* dumy return */
	}
	switch( n )
	{
	case 1:
	case 2:
		return( 1 );
	default:
		return( fibo(n-1) + fibo(n-2) );
	}
}

関数呼び出しの様子を見てみよう

#include <stdio.h>

/* i：呼び出した関数の実行番号、n：引数 */
int fibo( int i, int n )
{
static	int	cc = 0; /* 何回呼び出されたかを数えるカウンタ */
	int	c = ++cc; /* 今回の実行番号 */
	int	fn2, fn1;

	printf("%5d: fibo(%3d) called from %3dth, ", c, n, i );
	switch( n )
	{
	case 1:
	case 2:
		printf("fibo(%d) = 1 so return 1\n", n );
		return( 1 );
	default:
		printf("and call fibo(%3d) & fibo(%3d)\n", n-1, n-2 );
		fn1 = fibo(c,n-1);
		fn2 = fibo(c,n-2);
		printf("(%3d): fibo(%3d) = (fibo(%3d)=%3d) + (fibo(%3d)=%3d) so return %3d\n",
			c, n, n-1, fn1, n-2, fn2, fn1+fn2 );
		return( fn1 + fn2 );
	}
}

main()
{
	int	n, f;

        printf("Input a Number: ");
	scanf("%d", &n );

	/* mainの実行番号は 0 とする */
	printf("call fibo(%d) from main()\n", n );
	f = fibo( 0, n );
	printf("fibo(%d)=%d\n", n, f );
}
/* enf of fibotest.c */

帰納的なアルゴリズム

　クイックソート（quick sort）