[Algorithm] 2. 재귀

재귀 함수

- 재귀함수란 어떤 함수에서 자신을 다시 호출하여 작업을 수행하는 방식의 함수를 의미한다.

- 재귀함수를 작성할 때는 함수내에서 다시 자신을 호출한 후 그 함수가 끝날 때까지 함수 호출 이후의 명령문이

- 수행되지 않는다는 사실과 종료조건이 꼭  포함되어야한다는 부분을 인지해야 한다.

 

순열

def permutation(arr, r):
    arr = sorted(arr)
    used = [0 for _ in range(len(arr))]

    def generate(chosen, used):
        if len(chosen) == r:
            print(chosen)
            return

        for i in range(len(arr)):
            if not used[i]:
                chosen.append(arr[i])
                used[i] = 1
                generate(chosen, used)
                used[i] = 0
                chosen.pop()

    generate([], used)

 

순열은 어떻게 해도 nPr이기 때문에 시간복잡도는 O(n!)이다.

조합

def combination(arr, r):
    arr = sorted(arr)
    used = [0 for _ in range(len(arr))]

    def generate(chosen):
        if len(chosen) == r:
            print(chosen)
            return
        start = arr.index(chosen[-1]) + 1 if chosen else 0
        # nxt = 2부터 시작
        for nxt in range(start, len(arr)):
            if used[nxt] == 0 and (nxt == 0 or arr[nxt-1] != arr[nxt] or used[nxt-1]):
            # if used[nxt] == 0 :
                chosen.append(arr[nxt])
                used[nxt] = 1
                generate(chosen)
                chosen.pop()
                used[nxt] = 0
    generate([])

모든 조합의 합은 이항계수의 성질에 따라 한번 재귀호출시마다 2개의 함수를 호출하기 때문에 시간복잡도는 O(2^n)을 가진다.

피보나치

피보나치를 구현하는 방법은 여러가지가 있다.(재귀, for loop, dp, etc...)

재귀

def fibo(n: int) -> int:
    if n <= 2:
        return 1
    return fibo(n - 1) + fibo(n - 2)

한 단계씩 들어갈때마다 2개의 함수를 호출해야하기 때문에 시간복잡도는 O(2^n)이다.

 

DP

def fibo(n):
    cache = [0, 1]
    for i in range(2, n+1):
        cache.append(cache[i-1] + cache[i-2])
    return cache[n]

print(fibo(8))

n까지 한번만 계산하면 되기에 시간복잡도는 O(n)이다.

행렬 멱법같은 방법을 사용하면 시간복잡도를 O(logN)까지 줄일수는 있지만 여기서는 설명하지 않겠습니다.