1. 재귀 (recursion)

문제를 부분문제의 답을 이용해 해결하는 방법이다
ex) 0이상 정수 n에 대한 n!의 점화식

n!=1 if n=0  // base case
n!=n*(n-1)! if n > 0  // recursive case

1.1 재귀 함수 : 자기 자신을 호출하는 함수

ex1) 0이상 정수 n에 대한 n!

def factorial(n):
    if n == 0:
    	return 1
    else:
    	return n*factorial(n-1)

시간복잡도 : T(n) = k + T(n-k) : O(n)

ex2) 정수 a, b의 최대공약수

def gcd(a, b):
    if a%b == 0:
    	return b
    else:
    	return gcd(b, a%b)

시간복잡도 : T(a, b) = T(b, a%b) + 1 = T(a%b, b%(a%b)) + 2
a%b <= a/2 이므로 O(log max(a,b))

ex3) x^n 계산

def exp(x, n):
    if n == 0:
    	return 1
    else:
    	return x*exp(x,n-1)

시간복잡도 : O(n)

ex4) x^n 계산 2

def exp2(x, n):
    if n == 0:
    	return 1
    elif n%2 == 0:
    	tmp = exp2(x,n//2)
    	return temp*temp
    else:
    	return x*exp2(x, n-1)

시간복잡도 :

T(n) = 0             if n = 0
     <= T(n/2) + 2   if n > 0

T(n) <= T(n/2) + 2
     <= {T(n/2^2) + 2} + 2
     <= T(n/2^k) + 2k
     = T(1) + log n
     : O(log n)

2. 이진탐색

정렬되어 있는 배열에서 원소 찾는 방법. 중앙과 비교해 원소보다 작으면 왼쪽 탐색 크면 오른쪽 탐색한다
T(n) : O(log n)

def binarySearch(A, item, left, right):
    if left > right:    # item이 없는 경우
        return -1
    else:
        mid = (left+right) // 2
        if item == A[mid]:
            return mid
        elif item < A[mid]:
            return binarySearch(A, item, left, mid-1)
        else:
            return binarySearch(A, item, mid+1, right)

시간복잡도 :

T(n) = 1             if n = 1
     <= T(n/2) + 1   if n > 1
     
T(n) <= T(n/2) + 1
     <= [T(n/2^2) + 1] + 1
     <= T(n/2^k) + k
     = T(1) + log n
     : O(log n)

3. 하노이 탑 문제

단계
1) 막대기 1의 가장 큰 원반을 제외한 나머지 n-1개의 원반을 막대기 2로 옮긴다
2) 막대기 1의 가장 큰 원반을 막대기 3으로 옮긴다
3) 막대기 2에 놓여 있는 n-1개 원반을 막대기 3으로 옮긴다

def hanoiTower(n, source, dest, tmp):
    if (n == 1):
        print(f"Move disk from peg {source} to peg {dest}")
    else:
        hanoiTower(n-1, source, tmp, dest)    # 1단계
        print(f"Move disk from peg {source} to peg {dest}")  # 2단계
        hanoiTower(n-1, tmp, dest, source)    # 3단계

시간복잡도:

T(n) = 1            if n = 1
     = 2T(n-1) + 1  if n > 1
     
T(n) = 2T(n-1) + 1
     = 2[2T(n-2) + 1] + 1 = 2^2T(n-2) + 2 + 1
     = 2^2[2T(n-3) + 1] + 2 + 1
     = 2^k[T(n-k)] + 2^k - 1
     n-k = 1일때
     = 2^n-1[T(1)] + 2^n-1 - 1
     = 2^n-1 + 2^n-1 - 1
     = 2*(2^n-1) - 1 = 2^n - 1
     : O(2^n)