자료구조 - 재귀(Recursion)

재귀 (Recursion)

재귀는 그래프 탐색, 트리, DP(Dynamic Programming) 등 주요 자료구조와 알고리즘에 접목됩니다.

재귀는 자신을 정의할 때, 자기 자신을 재호출하는 것을 의미합니다.

재귀의 대표적인 예로는 팩토리얼과 피보나치가 있습니다.

 

재귀의 example

팩토리얼(factorial)

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

피보나치(fibonacci)

def fibo(n):
    if n == 1 or n == 2:
        return 1
    return fibo(n - 1) + fibo(n - 2)

 

재귀의 수학적 접근

앞선 factorial과 fibonacci를 보면 n 번째 함수를 n-1 번째 함수로 표현하는 것을 알 수 있습니다.

• factorial:  f(n) = n * f(n-1)
• fibonacci:  f(n) = f(n - 1) + f(n - 2)

이러한 식을 점화식이라고 합니다. 이것 역시 자기 자신을 참조하는 개념이 들어 있습니다.

그러나 계속 자기 자신을 참조하게 되면, 무한 루프에 빠질 수 있습니다.

 

따라서 무한 루프를 방지하기 위해 base case를 설정해주어야 합니다.

 

base case는 더 이상 자기 자신을 재참조 하지 않는 상황을 의미합니다.

팩토리얼(factorial)

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

base case:  f(1) = 1

 

피보나치(fibonacci)

def fibo(n):
    if n == 1 or n == 2:
        return 1
    return fibo(n - 1) + fibo(n - 2)

base case:  f(1) = 1, f(2) = 1

 

재귀의 시간 복잡도

재귀의 시간 복잡도 = 재귀 함수 호출 수 x (재귀 함수 하나 당) 시간 복잡도

팩토리얼(factorial)

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

• 재귀 함수 호출 수: N
• 재귀 함수 하나 당  시간 복잡도: O(1)
• 재귀의 시간 복잡도: O(n x 1)

피보나치(fibonacci)

def fibo(n):
    if n == 1 or n == 2:
        return 1
    return fibo(n - 1) + fibo(n - 2)

• 재귀 함수 호출 수: 2^n
• 재귀 함수 하나 당  시간 복잡도: O(1)
• 재귀의 시간 복잡도: O(2^n x 1)