Algorithm

[크래프톤 정글 week01] 재귀 함수

하루이2222 2024. 9. 7. 10:31

재귀 함수란

재귀 함수는 정의 단계 에서 자신을 재참조 하는 함수를 뜻 한다.

문제를 해결하기 위해 특정 분기 까지 계속 해서 자기 자신을 호출 한다. 이는 주로 반복문 구현 에 사용하게 된다.

흔히들 사용하게 되는 for,while,reduce등의 반복문등이 존재하는데 , 이러한 반복 문으로 구현이 가능한 로직은 재귀로도 구현이 가능하다.

재귀 함수 의 용도

재귀 함수는 큰 목표 작업을 여러 개의 작은 작업으로 쪼개서 해결할 수 있는 경우에 특히 유용하다. 이는 문제를 반복적으로 동일한 유형의 더 작은 문제로 나눌 수 있을 때 재귀 함수가 효과적이라는 의미다. 구체적으로, 재귀 함수는 다음과 같은 상황에서 유용하게 사용될 수 있다:

  1. 큰 문제를 더 작은 동일한 문제로 분할 가능할 때
    • 문제를 풀기 위해 동일한 종류의 더 작은 문제를 반복해서 해결해야 할 때, 재귀 함수를 사용하면 큰 문제를 작은 문제들로 쉽게 나눌 수 있다.
    • 예를 들어, n개의 항목이 있는 리스트의 합을 구하려고 할 때, 이 리스트를 두 개의 더 작은 리스트로 나누어 각각의 합을 구하고, 그 결과를 다시 합치는 방식으로 접근할 수 있다.
  2. 각 작은 문제의 해결 방법이 동일할 때
    • 큰 문제를 해결하는 데 필요한 방법이 작은 문제를 해결하는 방법과 동일한 경우, 재귀 함수는 자연스럽고 직관적이다.
    • 예를 들어, 이진 트리의 모든 노드를 순회할 때 각 노드에서 왼쪽 자식과 오른쪽 자식을 동일한 방식으로 순회하면 된다. 이처럼 재귀 함수는 트리나 그래프와 같은 자료구조의 탐색에 적합하다.
  3. 문제를 작은 부분으로 나눔으로써 문제의 크기를 줄여나갈 수 있을 때
    • 큰 문제를 더 작은 하위 문제로 나누면 각 하위 문제는 원래 문제보다 단순하고 해결하기 쉬워진다. 재귀적으로 계속 나누다 보면 결국 문제를 쉽게 풀 수 있는 "기저 사례(Base case)"에 도달하게 된다.
    • 예를 들어, n! (팩토리얼)은 n * (n-1)!로 계산할 수 있고, 이 식을 계속 적용하면 결국 1! 또는 0! 같은 매우 단순한 경우로 도달한다.
  4. 중복된 계산을 메모이제이션으로 최적화할 수 있을 때
    • 재귀 함수는 동일한 하위 문제를 여러 번 풀게 되는 경우가 많다. 이때 메모이제이션 기법을 사용하여 이미 계산한 하위 문제의 결과를 저장하고 재사용하면 효율성을 크게 높일 수 있다.
    • 예를 들어, 피보나치 수열의 F(n) = F(n-1) + F(n-2)를 계산할 때 F(n-1)과 F(n-2)를 여러 번 계산하게 된다. 메모이제이션을 사용하면 이러한 중복 계산을 피할 수 있다.

위 경우들의 예시

1. 큰 문제를 더 작은 동일한 문제로 분할 가능할 때

예시: 리스트의 합 구하기

리스트의 합을 구하는 문제는 큰 리스트를 더 작은 두 개의 리스트로 나눠 각각의 합을 구하고, 그 결과를 다시 합침으로써 해결할 수 있다.

def sum_list(lst):
    # Base case: 리스트가 비어 있으면 합은 0이다.
    if len(lst) == 0:
        return 0
    # Recursive case: 첫 번째 항목과 나머지 항목의 합을 더한다.
    return lst[0] + sum_list(lst[1:])

# 예제 실행
print(sum_list([1, 2, 3, 4, 5]))  # 결과: 15

위 예시에서 큰 문제(리스트의 전체 합)는 더 작은 동일한 문제(첫 번째 항목을 제외한 리스트의 합)로 분할되고, 이를 재귀적으로 해결한다.

2. 각 작은 문제의 해결 방법이 동일할 때

예시: 이진 트리의 모든 노드 순회

이진 트리의 모든 노드를 순회할 때, 각 노드는 동일한 방식으로 왼쪽과 오른쪽 자식을 순회하면 된다.

class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def inorder_traversal(node):
    if node is not None:
        # 왼쪽 서브트리 순회
        inorder_traversal(node.left)
        # 현재 노드 방문
        print(node.value, end=' ')
        # 오른쪽 서브트리 순회
        inorder_traversal(node.right)

# 예제 트리 생성 및 순회
root = TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4)))
inorder_traversal(root)  # 결과: 2 1 4 3

이 예시에서, 각 노드에 대해 동일한 작업(왼쪽 자식 순회 → 현재 노드 출력 → 오른쪽 자식 순회)을 반복함으로써 전체 트리를 순회한다.

3. 문제를 작은 부분으로 나눔으로써 문제의 크기를 줄여나갈 수 있을 때

예시: 팩토리얼 계산

팩토리얼 계산은 큰 문제를 더 작은 동일한 문제로 나누어 계산할 수 있다.

def factorial(n):
    # Base case: n이 0이면, 팩토리얼은 1이다.
    if n == 0:
        return 1
    # Recursive case: n * (n-1)의 팩토리얼
    return n * factorial(n - 1)

# 예제 실행
print(factorial(5))  # 결과: 120

n!은 n * (n-1)!로 계산될 수 있으므로, 큰 문제를 더 작은 문제로 점차 줄여가면서 해결한다.

4. 중복된 계산을 메모이제이션으로 최적화할 수 있을 때

예시: 피보나치 수열 계산

피보나치 수열에서 중복된 계산이 발생할 때 메모이제이션을 사용하여 최적화할 수 있다.

def fibonacci(n, memo={}):
    # Base case: n이 0 또는 1이면, 피보나치 수는 각각 0 또는 1이다.
    if n in memo:
        return memo[n]
    if n == 0:
        return 0
    elif n == 1:
        return 1
    # Recursive case: fibonacci(n-1) + fibonacci(n-2)
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]

# 예제 실행
print(fibonacci(10))  # 결과: 55

이 예시에서, 메모이제이션을 통해 중복 계산을 피하고 효율적으로 피보나치 수를 계산한다. F(n)을 계산할 때 이미 계산된 F(n-1)과 F(n-2)를 저장하고 재사용함으로써 시간 복잡도를 줄인다.

호출 스택

호출 스택(Call Stack)은 프로그램에서 함수 호출을 추적하고 관리하는 메모리 구조로, 함수가 호출될 때마다 해당 함수의 실행 정보를 저장하고, 함수 실행이 끝나면 이를 제거하여 원래 위치로 돌아가도록 하는 역할을 한다. 호출 스택은 LIFO(Last In, First Out, 후입선출) 구조를 따른다. 즉, 가장 마지막에 호출된 함수가 가장 먼저 반환된다.

재귀함수는 호출 스택과 상당히 유사한 동작 형태를 가진다.

재귀 함수와 호출 스택의 유사 점

  1. 함수 호출의 순서와 제어 흐름을 관리

재귀 함수는 자기 자신을 호출하는 함수로, 호출될 때마다 새로운 함수 호출이 발생한다. 각 재귀 호출은 현재 작업을 멈추고 새로운 작업을 시작하므로, 함수 호출의 순서와 흐름을 제어해야 한다.

  1. LIFO 후입 선출 의 구조

재귀 함수는 마지막에 호출된 함수가 가장 먼저 종료된다. 예를 들어, fibonacci(3)을 호출하면 fibonacci(3) → fibonacci(2) → fibonacci(1) 순으로 호출되고, 반대로 fibonacci(1) → fibonacci(2) → fibonacci(3) 순으로 종료된다. 이는 후입선출(LIFO) 구조로 작동한다.

호출 스택도 후입선출 구조로 작동한다. 스택에 마지막으로 추가된 함수 호출이 먼저 제거되며, 이는 재귀 호출이 반환될 때 함수들이 종료되는 순서를 정확히 유지하는 데 필요하다.

  1. 기저 사례(베이스 케이스)

재귀 함수는 종료 조건(기저 사례, Base Case)이 있어야 한다. 기저 사례가 없으면 재귀 호출이 무한히 반복되어 프로그램이 종료되지 않고, 호출 스택이 계속 쌓이다가 스택 오버플로(Stack Overflow)가 발생한다.
호출 스택은 함수 호출이 일어날 때마다 새로운 스택 프레임을 추가하고, 함수가 종료될 때 프레임을 제거한다. 기저 사례에 도달하지 못하는 재귀 함수는 호출 스택이 비워지지 않아 스택 오버플로를 초래한다.

재귀함수의 동작 순서

4!을 재귀함수를 통해 풀어보면서 동작 순서를 살표 보자

재귀 함수의 베이스 케이스는 `n = 0`과 `n = 1`인 경우이다. 위 코드에서 보이듯이, `n = 0`인 경우 재귀의 조건에 맞지 않으므로 `1`을 반환하게 된다. `n = 1`인 경우에는 `1 * f(0)`이 되므로 `1`을 반환하게 된다.

재귀 호출의 순서를 살펴보면 다음과 같다:

- `f(4) -> 4 * f(3)`
- `f(3) -> 3 * f(2)`
- `f(2) -> 2 * f(1)`
- `f(1) -> 1 * f(0)`

여기서 `f(0)`은 베이스 케이스에 의해 `1`을 반환한다.

따라서 `f(1) = 1`이 되고, 이를 바탕으로 `f(2) = 2`를 반환하게 된다. 이 값을 다시 위로 대입해 보면, `f(3) = 3 * 2 = 6`이 되는 것을 알 수 있다. 최종적으로, `f(4) = 4 * 6 = 24`라는 결과를 얻을 수 있다.

이렇게 재귀 호출을 통해 `f(4)`의 결과는 `24`가 된다.