재귀 recursion

수학적 귀납법의 기본형 :

p(1)이 참이고, p(n-1)->p(n)이 참이면, p(n)은 모든 자연수 n에 대해서 참이다

 

명제 p -> q의 의미

p가 참, q가 참 -> 전체 참

p가 참, q가 거짓 -> 전체 거짓

p가 거짓, q가 참 -> 전체 참 (Vacuously true) 

p가 거짓, q가 거짓 -> 전체 참 (Vacuously true)

 

Vacuously true란?

공허한 참, 말은 맞지만, 무의미하다는 뜻이다.

 

즉 p가 거짓이면 항상 Vacuously true 이다

하지만 p가 참일때는 증명을 해줘야 한다

 

int sum(int x)
{
    if(x<=0) return 0;
    return x + sum(x-1);
}

==> 1에서 x까지의 합에 대한 코드

==> 이해하기 위해서는 수학적 귀납법 필요

 

 

p(1)이 참이고

n=1 일 때, 1이 나오므로 참

 

, p(n-1)->p(n)이 참이면

n + sum(n-1) = sum (n) 이 맞으므로 참

 

, p(n)은 모든 자연수 n에 대해서 참이다

sum(n)은 참

 

 

The Complexity (코드가 돌아가는데 걸리는 시간)

T(n) = 1 + T(n-1)
 = 1 + 1 + T(n-2) = ... = n

T(n) = O(n) = n 보다 작은 것 =