재귀 함수

크게 다음의 두 부분으로 구성된다.

• basis part
• inductive part

basis part

• 기저 조건
• 탈출 조건
• 재귀 호출이 일어나지 않는 부분

inductive part

• 재귀 호출이 일어나는 부분
• 문제를 축소하는 부분

어떻게 작성하는가?

1. 함수의 정의(무슨 일을 하는가?)를 명확히 한다.
2. 똑같은 함수를 호출하되 변화가 생긴다.
   이는 parameter로 변화를 전달한다.
3. 기저 조건 찾기
   없으면 계속 재귀호출돼서 메모리 터짐
   
   

Reduction

중요한 것은 문제를 축소(reduction)해 나가는 것이다.
매 재귀 호출마다 문제가 축소되며 끝에는 basis part에 도달해여 하며,
이는 subproblem의 solution이 전체 문제의 solution이 되도록 함수를 설계해야 한다는 의미이기도 하다.

의외로 이상해 보이는 문제가 재귀에 대한 이해에 도움이 된다.