[자료구조/c언어] 명제와 수학적 귀납법을 재귀함수를 통해서 이해

명제와 수학적 귀납법을 재귀함수를 통해서 이해해보자.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
//수학적 귀납법 +  명제
int sum(int x)
{
	if (x <= 0) return 0;
	return x + sum(x - 1); //재귀 코드 이용
}
int main()
{
	int n;
	scanf("%d", &n);
	printf("%d", sum(n));
	return 0;
}
//아래 함수 대신 재귀 함수 이용
//int sum(int x)
//{
//	int i, S;
//	S = 0;
//	for (i = 1; i <= x; i++)
//		S += i;
//	return S;
//}

위의 sum 함수를 수학적 귀납법과 명제를 통해서 이해해보자.

수학적 귀납법은 p(1)이 참이고, p(n-1)이 참일때, p(n)이 참이면, p(n)은 모든 자연수 n에 대하여 참인 것을 나타내는 것이다.

명제의 경우 P->Q로의 명제가 있을 때,

P Q P->Q

TTT

TFF

FTT

FFT

의 진리값을 갖는다.

수학적 귀납법의 정의에서 노란배경색 부분이 "참이면 참" 을 보는 이유는 앞 부분의 명제가 거짓일 때는 뒤 부분의 명제의 진리값에 관계없이 전체 명제가 참이 되기 때문에 의미가 없다. 따라서 참이면 참이라는 부분만 보게 된다.

이에 따라 sum함수를 보면,

base)

x = 1일때, sum함수는 return 1 + sum(0)이고, sum(0) = 0이므로, sum함수는 결과적으로 1을 리턴한다.

seep)

sum(x-1)이 1+2+ ... + x-1 의 값을 리턴하면, sum(x) 가 1+2+ ... + x-1 + x 의 값을 리턴하는지 보면 된다.

sum(x-1)은 위의 값을 리턴하고, sum(x) = x + sum(x-1) 이므로, 위의 값을 리턴한다.

따라서 , 결과적으로 수학적 귀납법에 따라 위 sum함수가 모든 인자 x에 대해서 성립함을 알 수 있다.