末尾再帰

tailRecursion.c

/* 末尾再帰　tailRecursion.c
	再帰的な関数recurを徐々に非再帰的にしていく
 */
#include <stdio.h>

// 真に再帰的な関数recur
void recur(int n)
{
	if (n > 0) {
		recur(n - 1);
		printf("%d ", n);
		recur(n - 2);
	}
}
/* 入力が４のとき、最終的な出力は
	1 2 3 1 4 1 2
となる */

// 末尾再帰を除去
void recur2(int n)
{
Top:
	if (n > 0) {
		recur(n - 1);
		printf("%d ", n);
		// 関数の最後に行われる再帰呼び出しはたやすく除去できる
		n = n - 2;
		goto Top;
	}
}

// 再帰を除去
void recur3(int n)
{
	int stk[100]; 	// スタック
	int ptr = 0; 	// スタックポインタ
Top:
	if (n > 0) {
		stk[ptr++] = n;	// nの値をプッシュ
		n = n - 1;
		goto Top;
	}
	if (ptr > 0) {		// スタックが空でなければ
		n = stk[--ptr];	// 値を保存していたnをポップ
		printf("%d ", n);
		n = n - 2;
		goto Top;
	}
}

int main(void)
{
	int x;
	printf("整数を入力せよ：　");
	scanf("%d", &x);
	recur(x);
	return 0;
}