[Computational Thinking] 재귀함수를 제대로 읽는 법

재귀는 직관대로 따라 들어가며 읽는 것이 아니라, 수학적 귀납법을 통해 증명해야 한다.

수학적 귀납법 : 𝑃(1)이 참이고 , 𝑃(𝑛)→𝑃(𝑛+1)이 참이면 𝑃(𝑛)은 모든 자연수 𝑛에 대해서 참이다.

 

수학적 귀납법에서 필요한 것은 𝑃(𝑛)→𝑃(𝑛+1)이 참임을 보이는 것 뿐이므로 𝑃(𝑛)이 정말로 참일 필요는 없음.

즉, 𝑃(𝑛)은 참이라고 가정하고 𝑃(𝑛+1)를 증명하기만 하면 된다.

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

ex) 위 예시에서 sum(x-1)를 블랙박스로 보아야 한다.