Meaningful

Meaningful

Greeting :)

[알고리즘]Recursion(재귀) 알고리즘

Date:     Updated:

카테고리:

재귀(Recursion)

귀납적 추론 vs 연역적 추론 vs 절차지향적 추론

귀납적 추론(Inductive Reasoning)은 구체적인 사례나 경험을 통해 일반적인 원리나 법칙을 도출하는 사고방식이다. 즉, 개별적인 관찰이나 실험을 바탕으로 일반적인 결론을 내리는 방식이다. 귀납적 추론은 확률적인 결론을 도출하며, 반드시 참이라고 보장할 수는 없지만 반복된 경험이나 사례를 통해 결론이 도출된다.

관찰: “이번 여름 동안 관찰한 백조들은 모두 흰색이었다.”
결론: “모든 백조는 흰색일 것이다.”(단, 이는 확률적 결론으로, 백조가 항상 흰색이라고 보장할 수는 없음.)

  • 귀납적 추론의 특징
    • 개별적인 사례로부터 일반적 결론을 도출
    • 결론이 확률적이며, 항상 참이라고 보장할 수는 없음

연역적 추론(Deductive Reasoning)은 일반적인 원리나 법칙을 기반으로 특정 결론을 도출하는 사고방식이다. 즉, 이미 알고 있는 사실이나 법칙을 전제로 하여 이를 바탕으로 논리적으로 필연적인 결론을 이끌어내는 방식이다. 연역적 추론의 결론은 전제가 참이라면 반드시 참이 된다.

전제 1: “모든 사람은 죽는다.”
전제 2: “소크라테스는 사람이다.”
결론: “소크라테스는 죽는다.”(전제가 참이므로 결론도 반드시 참.)

  • 연역적 추론의 특징
    • 일반적 원리로부터 특정 결론을 도출
    • 전제가 참이면 결론도 반드시 참

절차지향적 추론(Procedural Reasoning)은 문제를 해결하기 위해 일련의 단계나 절차를 따르는 방식이다. 이는 순차적인 절차를 기반으로 문제를 단계적으로 해결하는 접근법으로, 각 단계는 이전 단계의 결과를 사용하여 다음 단계를 수행한다. 프로그래밍에서 절차지향적 사고는 알고리즘을 순서대로 실행하는 방식으로 구현된다.

단계 1: “재료를 준비한다.”
단계 2: “야채를 자른다.”
단계 3: “냄비에 물을 끓인다.”
단계 4: “재료를 차례대로 넣고 요리한다.” (각 단계는 순차적으로 진행되며, 순서가 중요.)

  • 절차지향적 추론의 특징
    • 일련의 절차나 단계에 따라 문제를 해결
    • 순차적으로 문제를 해결하며, 각 단계가 순서대로 중요함

재귀 알고리즘의 특징

재귀 알고리즘에서 귀납적 사고는 작은 하위 문제들이 해결되면 더 큰 문제도 해결될 수 있다는 가정에 기반한다. 즉, 특정 문제를 해결하기 위해 그보다 더 작은 문제들이 해결된다고 가정하고, 이를 통해 전체 문제의 해결 방법을 유추해 나가는 방식이다. 이처럼 귀납적 사고는 개별적인 사실로부터 일반적인 규칙이나 법칙을 발견하는 데 유용하며, 재귀적 접근 방법에서도 중요한 역할을 한다.

A technique that breaks down a problem into smaller subproblems to obtain a solution.

재귀 함수는 기본 사례(Base Case)와 유도 단계(Inductive Step)로 구성된다. 기본 사례는 가장 단순한 상황에서 재귀 호출을 종료하는 조건을 제공하여 알고리즘이 무한히 반복되지 않도록 한다. 유도 단계는 문제를 더 작은 하위 문제로 나누어 해결하며, 하위 문제의 해답을 통해 전체 문제의 해답을 구성해 나가는 과정이다.

따라서 재귀 알고리즘을 사용할 때는 평소의 절차 지향적 사고에서 벗어나 귀납적 사고를 바탕으로 문제를 이해하고 접근하는 것이 필요하다. 이를 통해 복잡한 문제를 재귀적으로 해결할 수 있다.

문제1: 피보나치 수열(Fibonacci Sequence)

1

대표적인 재귀 알고리즘의 문제는 바로 피보나치 수열이다. 피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 처음 여섯 항은 각각 1, 1, 2, 3, 5, 8이다. 편의상 0번째 항을 0으로 두기도 한다.

$$F(n) = \begin{cases} 0 & \text{if } n = 0 \\ 1 & \text{if } n = 1 \\ F(n-1) + F(n-2) & \text{if } n \geq 2 \end{cases}$$

피보나치 수열은 위의 수식 \(F(n)\)을 재귀하는 것이다. 여기서 기본 사례(Base case)와 유도 사례(Inductive Step)을 정의할 수 있다. 이를 코드로 표현하면 다음과 같다.

def fib(n):
    # Base cases
    if n <= 1:
        return n
    # Inductive step
    else:
        return fib(n - 1) + fib(n - 2)

# 예시: n이 10일 때 10번째 피보나치 수를 출력
print(f"Fibonacci n=10: {fib(10)}")

# n이 1부터 10까지의 피보나치 수를 순차적으로 출력
for i in range(1, 11):
    print(f"Fibonacci({i}) = {fib(i)}")

Fibonacci n=10: 55

Fibonacci(1) = 1
Fibonacci(2) = 1
Fibonacci(3) = 2
Fibonacci(4) = 3
Fibonacci(5) = 5
Fibonacci(6) = 8
Fibonacci(7) = 13
Fibonacci(8) = 21
Fibonacci(9) = 34
Fibonacci(10) = 55

문제2: Reverse String Recursively

문제: 주어진 문자열 s의 크기가 n일 때, 이 문자열을 역순으로 출력하라.

  • 함수: reverse(s[0..n-1])
  • reverse(s[1..n-1])는 하위 문자열[\(1, \dots, n-1\)]을 역순으로 출력한다.
  • print(s[0]) 문자열의 첫 번째 문자를 출력한다.

기본 사례(Base Case)
재귀 함수가 문자열의 끝에 도달했을 때 종료해야 한다. 즉, 인덱스 i가 문자열의 길이 len(s)와 같거나 클 때, 재귀 호출을 종료한다. 이는 문자열의 모든 문자가 처리되었음을 의미한다.

유도 단계(Inductive Case)
문자열의 첫 번째 문자를 제외한 나머지 부분을 재귀적으로 처리한다. helper(i + 1, s)를 호출하여 다음 인덱스로 진행하며, 재귀 호출이 반환된 후에 현재 인덱스의 문자를 출력한다. 이를 통해 문자열이 역순으로 출력되도록 한다.

def helper(i, s):
    # Base case: 문자열의 끝에 도달하면 종료한다
    if i >= len(s):
        return
    # Inductive case: 다음 인덱스로 재귀 호출을 한다
    helper(i + 1, s)
    # 현재 인덱스의 문자를 출력한다
    print(s[i], end='')

def reverse(s):
    # 재귀를 시작하는 초기 호출이다
    helper(0, s)

reverse("hello") # "olleh"

reverse 함수는 helper 함수를 호출하여 문자열의 역순 출력을 시작한다. helper 함수는 재귀적으로 문자열의 끝까지 탐색하고, 반환되면서 각 문자를 출력하여 최종적으로 문자열을 역순으로 출력한다.

재귀 함수의 시표적인 재귀 알고리즘의 문제는 바로 피보나치 수열이다. 피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 처음 여섯 항은 각각 1, 1, 2, 3, 5, 8이다. 편의상 0번째 항을 0으로 두기도 한다.

$$F(n) = \begin{cases} 0 & \text{if } n = 0 \\ 1 & \text{if } n = 1 \\ F(n-1) + F(n-2) & \text{if } n \geq 2 \end{cases}$$

피보나치 수열은 위의 수식 \(F(n)\)을 재귀하는 것이다. 여기서 기본 사례(Base case)와 유도 사례(Inductive Step)을 정의할 수 있다. 이를 코드로 표현하면 다음과 같다.

def fib(n):
    # Base cases
    if n <= 1:
        return n
    # Inductive step
    else:
        return fib(n - 1) + fib(n - 2)

# 예시: n이 10일 때 10번째 피보나치 수를 출력
print(f"Fibonacci n=10: {fib(10)}")

# n이 1부터 10까지의 피보나치 수를 순차적으로 출력
for i in range(1, 11):
    print(f"Fibonacci({i}) = {fib(i)}")

Fibonacci n=10: 55

Fibonacci(1) = 1
Fibonacci(2) = 1
Fibonacci(3) = 2
Fibonacci(4) = 3
Fibonacci(5) = 5
Fibonacci(6) = 8
Fibonacci(7) = 13
Fibonacci(8) = 21
Fibonacci(9) = 34
Fibonacci(10) = 55

문제2: Reverse String Recursively

문제: 주어진 문자열 s의 크기가 n일 때, 이 문자열을 역순으로 출력하라.

  • 함수: reverse(s[0..n-1])
  • reverse(s[1..n-1])는 하위 문자열[\(1, \dots, n-1\)]을 역순으로 출력한다.
  • print(s[0]) 문자열의 첫 번째 문자를 출력한다.

기본 사례(Base Case)
재귀 함수가 문자열의 끝에 도달했을 때 종료해야 한다. 즉, 인덱스 i가 문자열의 길이 len(s)와 같거나 클 때, 재귀 호출을 종료한다. 이는 문자열의 모든 문자가 처리되었음을 의미한다.

유도 단계(Inductive Case)
문자열의 첫 번째 문자를 제외한 나머지 부분을 재귀적으로 처리한다. helper(i + 1, s)를 호출하여 다음 인덱스로 진행하며, 재귀 호출이 반환된 후에 현재 인덱스의 문자를 출력한다. 이를 통해 문자열이 역순으로 출력되도록 한다.

def helper(i, s):
    # Base case: 문자열의 끝에 도달하면 종료한다
    if i >= len(s):
        return
    # Inductive case: 다음 인덱스로 재귀 호출을 한다
    helper(i + 1, s)
    # 현재 인덱스의 문자를 출력한다
    print(s[i], end='')

def reverse(s):
    # 재귀를 시작하는 초기 호출이다
    helper(0, s)

reverse("hello") # "olleh"

reverse 함수는 helper 함수를 호출하여 문자열의 역순 출력을 시작한다. helper 함수는 재귀적으로 문자열의 끝까지 탐색하고, 반환되면서 각 문자를 출력하여 최종적으로 문자열을 역순으로 출력한다.

재귀 함수의 시·공간 복잡도

재귀 함수에서

  • 시간 복잡도는 재귀 호출 횟수와 각 호출에서 수행되는 계산의 시간 복잡도로 결정된다.
  • 공간 복잡도는 재귀 호출을 추적하기 위한 스택 공간과 전역 변수에 할당된 힙 공간으로 나뉜다.

시간 복잡도에서 재귀 알고리즘의 복잡도 \(O(T)\)는 재귀 호출 횟수 \(R\)과 각 호출에서의 계산 시간 복잡도 \(O(s)\)의 곱으로 표현된다. 예를 들어, 2번 문제의 문자열을 역순으로 출력하는 재귀 함수의 경우, 문자열의 길이 \(n\)만큼 재귀적으로 호출되며, 각 호출에서 한 번의 문자 접근이 이루어지므로 시간 복잡도는 \(O(n)\)이다.

  • 재귀 알고리즘의 시간 복잡도: \(O(T) = R \times O(s)\)
  • reverse함수의 시간 복잡도: \(O(reverse) = n \times O(1) = O(n)\)

1

공간 복잡도는 재귀(Recursion-related)와 비재귀 관련 공간(Non-recursion-related)으로 구성된다. 재귀 관련 공간은 재귀 함수 호출을 추적하기 위해 사용되는 스택 공간이며, 호출 깊이에 비례하여 증가한다. 비재귀 관련 공간은 주로 전역 변수에 할당되는 힙 공간으로, 재귀 호출과 무관하게 고정된 크기를 가진다. 이 두 요소가 결합되어 재귀 함수의 전체 공간 복잡도를 결정한다.

  • 재귀 알고리즘의 공간 복잡도: 재귀 관련 공간(Recursion-related space) + 바재귀 관련 공간(Non-recursion-related space)
    • 재귀 관련 공간: 재귀 함수 호출을 추적하기 위한 스택(stack) 공간
    • 비재귀 관련 공간: 전역 변수에 할당되는 힙(heap) 공간

문제 3: Tail Recursion

문제: 주어진 리스트의 숫자 합을 계산(재귀적으로 접근)

이 문제를 통해서 재귀 호출이 함수의 마지막 명령으로 사용되는 Tail Recursion(꼬리 재귀)와 그렇지 않은 Non-Tail Recursion(일반 재귀) 방식의 차이를 설명할 수 있다.

Tail Recursion는 재귀 호출이 함수의 마지막 명령어로 사용되는 재귀 함수이다. 이 경우, 함수 내부에 하나의 재귀 호출만 있어야 한다. 예를 들어, 리스트의 합을 계산하는 Tail Recursion 함수에서는 모든 계산이 재귀 호출 전에 수행되며, 재귀 호출이 최종 명령으로 나타난다.

Non-Tail Recursion는 재귀 호출 후에 추가적인 계산이 있는 재귀 함수이다. 리스트의 합을 계산하는 일반 재귀 함수에서는 재귀 호출이 완료된 후에 반환된 값을 사용하여 추가 계산을 수행한다. 이러한 경우, 함수가 재귀적으로 호출된 후에도 스택에 정보가 남아 있어야 하므로 메모리 사용이 증가한다.

from typing import List

def sumTailRecursion(ls: List[int]) -> int:
    def helper(ls, acc):
        if len(ls) == 0:
            return acc
        # 꼬리 재귀: 재귀 호출이 최종 명령어로 사용된다
        return helper(ls[1:], ls[0] + acc)
    
    return helper(ls, 0)

def sumNonTailRecursion(ls: List[int]) -> int:
    # 리스트의 합을 계산한다
    if len(ls) == 0:
        return 0
    # 일반 재귀: 재귀 호출 후에 추가 계산이 있다
    return ls[0] + sumNonTailRecursion(ls[1:])

# 테스트 리스트
test_list = [1, 2, 3, 4, 5]

# 꼬리 재귀를 사용한 리스트 합 계산
tail_sum = sumTailRecursion(test_list)
print(f"Tail Recursion Sum: {tail_sum}")  # 출력: Tail Recursion Sum: 15

# 일반 재귀를 사용한 리스트 합 계산
non_tail_sum = sumNonTailRecursion(test_list)
print(f"Non-Tail Recursion Sum: {non_tail_sum}")  # 출력: Non-Tail Recursion Sum: 15

Tail Recursion Sum: 15
Non-Tail Recursion Sum: 15

Tail Recursion의 장점

  • Tail Recursion은 재귀 호출 동안 스택 오버헤드가 축적되는 것을 방지할 수 있다.
  • 각 재귀 호출이 동일한 스택 프레임을 재사용할 수 있어 메모리 사용이 최소화된다.

예를 들어, 함수가 재귀적으로 호출되는 순서가 \(f(x_1) \to f(x_2) \to f(x_3)\)일 때, 꼬리 재귀가 사용되면 다음과 같은 이점이 있다:

  1. \(f(x_1)\)를 호출할 때, \(f(x_2)\)를 호출하기 위해 스택 공간이 할당된다.
  2. \(f(x_2)\)는 다시 재귀적으로 \(f(x_3)\)을 호출한다.
  3. \(f(x_3)\)이 기본 사례(Base Case)에 도달하면, 함수는 이전 호출로 돌아가지 않고 바로 결과를 최초 호출자에게 반환한다.

따라서 꼬리 재귀는 메모리 효율적이며, 재귀 깊이가 깊을 때 스택 오버플로우를 방지할 수 있는 중요한 기법이다.

재귀 알고리즘은 절차 지향적 알고리즘에 비해 공간 효율성이 떨어질 수 있으며, 각 재귀 호출은 스택에 새로운 레이어를 추가하기 때문에 깊이가 \(n\)인 경우 최소 \(O(n)\)의 공간을 사용한다. 재귀 알고리즘을 반복적으로 구현하는 것은 더 복잡하지만, 모든 재귀 알고리즘은 반복적으로 구현될 수 있다. 의심스러울 때는 재귀 관계를 작성하는 것이 도움이 된다.

문제 4: 문자열 순열(Permutation)

1

문제: 문자열의 모든 순열을 출력

  • Base Case (기본 사례)
    • 문자열의 길이가 1인 경우, 예를 들어 “a”라는 문자열이 주어지면, 순열은 [“a”] 하나뿐이다. 이는 기본 사례로서, 길이가 1인 문자열의 순열을 다루는 가장 단순한 형태이다.
  • Complex Cases (복잡한 사례)
    • 길이가 2인 문자열 “ab”에 대한 순열은 [“ab”, “ba”]이다. 길이가 3인 문자열 “abc”의 경우, 이전 단계의 결과에 새 문자 “c”를 삽입하는 방식으로 모든 가능한 위치에 문자를 추가하여 모든 순열을 생성할 수 있다.
    • 예를 들어, P(“abc”)를 “abc”에 대한 순열로 정의할 때, P(“ab”)에 있는 각 문자열의 모든 위치에 “c”를 삽입하여 P(“abc”)를 생성할 수 있다.
    • P(“ab”) = [“ab”, “ba”]
    • P(“abc”)는 “c”를 P(“ab”)의 모든 문자열에 삽입하여 [“cab”, “acb”, “abc”, “cba”, “bca”, “bac”]를 얻는다.
from typing import List

def permute(s: str) -> List[str]:
    # Base case: 길이가 1인 문자열의 순열은 자기 자신이다
    if len(s) == 1:
        return [s]

    permutations = []
    
    # 모든 문자에 대해 해당 문자를 고정하고 나머지 문자로 재귀적으로 순열을 생성
    for i, char in enumerate(s):
        # 현재 문자를 제외한 부분 문자열
        remaining = s[:i] + s[i+1:]

        # 재귀 호출을 통해 나머지 부분 문자열의 순열을 구함
        for perm in permute(remaining):
            # 현재 문자를 앞에 추가하고 결과 리스트에 저장
            permutations.append(char + perm)

    return permutations

# 예시: 문자열 "abc"의 모든 순열을 출력
print(permute("abc"))

['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

문제 5: Power Set

문제: 모든 subset을 반환

  • Example
    • Input: [1, 2, 3]
    • Output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

Base Case (기본 사례)

  • 입력 리스트 arr가 비어 있을 때, 즉 len(arr) == 0일 때이다.
  • 이 경우, 부분 집합은 빈 집합 하나뿐이므로 [[]]를 반환한다.

Inductive Case (유도 단계)

  • 입력 리스트 arr가 비어 있지 않을 때, 즉 len(arr) > 0일 때이다.
  • 리스트의 마지막 원소를 제외한 부분 집합을 재귀적으로 계산한 후, 이 부분 집합에 마지막 원소를 추가하여 새로운 부분 집합을 생성한다.
  • 기존 부분 집합과 새로운 부분 집합을 결합하여 최종적으로 반환한다.

[재귀적 구현]

def power_set(arr):
    # Base case: 입력 리스트가 비어 있을 때 부분 집합은 빈 집합 하나뿐이다.
    if len(arr) == 0:
        return [[]]

    # Inductive case: 마지막 원소를 제외한 부분 집합을 재귀적으로 계산한다.
    sets = power_set(arr[:-1])
    new_sets = []

    # 기존 부분 집합에 마지막 원소를 추가하여 새로운 부분 집합을 생성한다.
    for set1 in sets:
        set2 = set1.copy()
        set2.append(arr[-1])
        new_sets.append(set2)

    # 기존 부분 집합과 새로운 부분 집합을 결합하여 반환한다.
    sets.extend(new_sets)
    return sets

if __name__ == "__main__":
    # Jupyter 환경에서는 명령줄 인수를 사용할 수 없으므로 직접 리스트를 정의한다.
    arr = [1, 2, 3]  # 테스트를 위한 하드코딩된 리스트
    output = power_set(arr)
    print(output)

    arr = [4,7,9,6]
    output = power_set(arr)
    print(output)

[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
[[], [4], [7], [4, 7], [9], [4, 9], [7, 9], [4, 7, 9], [6], [4, 6], [7, 6], [4, 7, 6], [9, 6], [4, 9, 6], [7, 9, 6], [4, 7, 9, 6]]

[재귀적 구현 + 반복적 구현]

# Power Set
# Cracking the Coding Interview: 189 Programming Questions & Solutions, Chapter 8, p135

def powerSetRecursive(A):
  if not A: return [[]]
  else:
    sets = powerSetRecursive(A[:-1])
    newSets = []
    for curr in sets:
      new = curr.copy()
      new.append(A[-1])
      newSets.append(new)
    sets.extend(newSets)
    return sets

def powerSetIterative(A):
  sets = [[]]
  for n in A:
    newSets = []
    for curr in sets:
      new = curr.copy()
      new.append(n)
      newSets.append(new)
    sets.extend(newSets)
  return sets

if __name__ == "__main__":
  A = [1, 2, 3]
  B = [4,7,9,6]
  output = powerSetRecursive(A)
  print(output)
  output = powerSetIterative(B)
  print(output)

[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
[[], [4], [7], [4, 7], [9], [4, 9], [7, 9], [4, 7, 9], [6], [4, 6], [7, 6], [4, 7, 6], [9, 6], [4, 9, 6], [7, 9, 6], [4, 7, 9, 6]]



Reference

[1] 피보나치 수열: 정의, 공식, 목록 및 예
[2] Lecture: ITG6022 Computational Problem Solving

Algorithm 카테고리 내 다른 글 보러가기

댓글 남기기

최근 글 10 개 :)