재귀함수는 하나 이상의 기본 사례에 의해 정의되고, 더 작은 인수를 사용하여 자기 자신으로 정의되는 함수이다. Methods for sloving recurrences: 재귀함수를 푸는 메서드Repeated Substitution Method(반복 치환) 위 재귀함수식을 어디서 많이 봤을 텐데, merge sort에서 등장했었다.반복 치환 메서드는 말 그대로 치환을 반복하면서 식을 유도해나가는 방식이다. merge sort 알고리즘은 먼저 원소가 한개 남을 때까지 배열을 쪼갠다.$T(n) = 2T(n/2) + n$의 식을 쪼개보면,$T(n) = 2(2T(n/2^{2}) + n/2) + n = 2^{2} T(n/2^{2}) + 2n$이다.한번 더 쪼개보자.$T(n) = 2^{2}(2T(n/2^{3}) + ..
