재귀(Recursion): 재귀함수
재귀함수란 어떤 함수 내부에서 한 번 이상 자신의 함수를 호출하는 경우에 그 함수이다.
이때 함수를 '알고리즘'으로 바꿔 이해할 수도 있다.
예1: 1+2+3+ + N 1부터 n까지 더하는 문제가 있다고 하면,
sum(n) = sum(n-1) + n : n-1까지 더하고 n을 더한 값으로 표현할 수 있다.
def sum(n):
if n == 1: return 1
return sum(n-1) + n sum(4) = sum(3) + 4 = sum(2) + 3 + 4 = sum(1) + 2 + 3 + 4 = 1 + 2 + 3 + 4 = 10
호출을 하며 아래로 내려가는 것은 재귀호출 의 과정이고, 반환하며 위로 올라간다면 return 한다고 본다.
수행시간을 T(n) 이라하면 비교를 한 번 하고, 덧셈 연산 한 번, sum(n-1) 계산하는데 걸리는 T(n-1) 이 걸린다. 따라서
T(n) = T(n-1) + c (2가 상수로 변한 c) 를 수행시간이라 할 수 있다. 이는 점화식이므로
T(n-2) + 2c ... = T(1) + (n-1)c = (1을 더하는데는 상수시간이므로) c * n
따라서 O(n) 이다. (더하기를 n번 하는 것!)
-
n == 1 테스트: 바닥조건 base case T(1) = 1 or c
-
n != 1 재귀호출: T(n) 점화식
sum(a,b) = a + (a+1) + ... + (b-1) + b
sum(3, 8) = 3 + 4 + 5 + 6 + 7 + 8
sum(3,5) + sum(6,8) 과 같다. (반씩 나눠 재귀호출하는 방법) 이때 5 = (3+8) // 2 이다.
def sum(a,b):
if a == b: return a
if a > b : return 0
m = (a+b) // 2
return sum(a, m) + sum(m+1, b)T(n) 은 어떻게 될까? 비교, 비교, 대입, 덧셈, 나눗셈, 덧셈이 있다. + 재귀호출 두 번. 각각 재귀호출의 시간복잡도는 전체였을 때 T(n) 이므로 반으로 나눈 각각은 T(n/2) 이다.
따라서 T(n) = 2 * T(n/2) + c, T(1) = c or 1
n = 2^k (2의 몇 승 형태라 가정하면) 이라면
2 T(n/2) + C = 2 ( 2 T (n/2^2) + c ) + c
= 2^2T(n/2^2) + 2c + c
= 2^kT(n/2^k) + c(1 + 2 + 2^2 + + 2^(k-1))
= c * 2^k + c ( 2^k - 1) / (2 - 1 ) = 2c2^k - c = 2cn - c
O(n) = n 이다. (최고차항만 남김)
따라서 두 문제 모두 O(n) 만큼의 시간이 걸린다는 것을 확인할 수 있다.
reverse 함수: A = [1,2,3,4,5] 를 [5,4,3,2,1] 로 만드는 것!
reverse(A) = reverse(A[1:]) + A[0]
= reverse(A[1:]) + A[:1]
T(n) = T(n-1) + c = O(n)
reverse(A, start, stop) = A[start] +... +, A[stop-1]
앞뒤를 서로 바꾼다.
A[stop-1] A[start+1] ... A[stop-2] A[start]
T(n) = T(n-2) + c = T(n-4) + 2c ... = T(1) + n/2 * c
따라서 O(n) 이다.
