동적프로그래밍과 재귀함수에 대한 알고리즘 문제가 가장 어려운 것 같다. 오늘 이에 재귀함수 문제에 대해 알고리즘을 만들때 항상 마음에 두고 있어야 했으면 하는 원칙들을 넣으려 한다.

발상

재귀함수가 어려운 이유는 재귀가 일어나는 안쪽에서 어떻게 진행이 되는가 에 대해서 알기 어렵기 때문이다. 물론 컴퓨터 사고 능력이 좋아 알면 좋겠지만, 재귀가 3중, 4중으로 겹겹이 진행되면 머리가 아파오고 포기를 하고 싶어 진다.

그러나 재귀함수에써 진짜 핵심은 재귀함수를 사용함으로써 재귀함수가 하는 역할을 파악하는 것이다.

우리가 굳이 재귀함수를 다 헤쳐보았을 때 어떤 일을 하는 지에 대해서는 궁금해 할 필요가 없다. 어차피 컴퓨터가 해주는 일인데 굳이 궁금해 할 필요가 없는 것이다.

재귀함수는 수학적 귀납법으로 이해하면 좋다.

수학적 귀납법은 다음과 같은 흐름으로 진행 된다.

1) n = 1일때 명제를 증명한다. 2) n = k일때 명제가 성립한다고 가정한다. 3) n = k + 1일때 명제가 성립함을 2)를 이용해 증명한다.

여기서 핵심은 n을 모든 자연수에 대해서 일일이 증명하지 않고, n = k 일 때 성립한다고 가정해버린후 n = k + 1일 때 명제가 성립함을 2)와의 관계를 이용하여 증명한다.

주의! 재귀함수를 공부할 때 재귀 함수 안에서 일어나는 일을 이해하려고 하는 것은 n이 모든 자연수일 때 다 대입하여서 이해하려는 것과 같은 것이다.

따라서 재귀함수도 같은 원리로 이해하면 편하다.

1) n = 1(초기값)에 대하여 함수안에 식을 구현해 놓은다. 2) n = k 일때 함수가 성립한다고 가정한다. 3) n = k + 1일때 2)와 연관성을 탐구한 후 코딩한다

이때 재귀함수와 수학적 귀납법의 차이점은

재귀함수를 작성할 때는 3)에서 분기문이라던가, 부수적인 코딩을 생각해줘야한다는 정도이다. 언제까지나 기본 원리는 같다.

다만 재귀함수의 stack 메모리 Space에 대해 allocation은 stack형식으로 증가하게 된다.