[ 알고리즘 ] 재귀(Recursion)

728x90

재귀란?

재귀(recursion)은 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻한다.

재귀

재귀(Recursion)는 함수가 자기 자신을 호출하는 프로그래밍 기법입니다.

주로 복잡한 문제를 더 작은 부분 문제로 나누어 해결할 때 유용합니다.

재귀 함수는 기본적으로 두 가지 부분으로 이루어져 있습니다

기저 조건(Base Case)

함수가 자기 자신을 호출하여 문제를 더 작은 부분으로 나누는 단계입니다.

def factorial(n):
    # 기저 조건: n이 1 이하일 때, 1을 반환하여 재귀를 멈춤
    if n <= 1:
        return 1

재귀 단계(Recursive Step)

함수가 자기 자신을 호출하여 문제를 더 작은 부분으로 나누는 단계입니다.

def factorial(n):
    # 기저 조건: n이 1 이하일 때, 1을 반환하여 재귀를 멈춤
    if n <= 1:
        return 1
    # 재귀 단계: n * factorial(n-1)
    else:
        return n * factorial(n - 1)

왜 재귀를 쓰나?

- 재귀를 사용한 피보나치 수열을 구하는 코드

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

print(factorial(5))  # 출력: 120

장점

간결성: 문제를 수학적 정의에 가깝게 표현할 수 있습니다.
가독성: 알고리즘의 로직을 직관적으로 이해하기 쉽습니다.
구현 용이성: 복잡한 문제를 작은 부분 문제로 나누어 해결할 수 있습니다.

주의점

중복 계산: 동일한 하위 문제를 여러 번 해결할 수 있으며, 이로 인해 시간 효율성이 저하됩니다
메모리 사용량: 각 재귀 호출마다 스택 메모리에 호출 정보가 저장되므로 큰 입력 값에 대해서는 스택 오버플로우(Stack Overflow)를 일으킬 수 있습니다.

개선방법

메모이제이션(memoization)
컴퓨터 프로그램이 동일한 계산을 반복해서 수행하는 것을 방지하여 계산 시간을 개선하는 기법입니다.

- 메모제이션과 재귀를 활용한 피보나치 수열을 구하는 코드

def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]

print(fibonacci(10))  # 출력: 55

기존의 단점 해결

중복 계산 방지:
- 코드에서 볼 수 있듯이, 메모이제이션을 사용하면 피보나치 수열의 각 수는 한 번만 계산됩니다.
- 이 결과는 memo 딕셔너리에 저장되어, 같은 수를 다시 계산해야 할 때 이미 저장된 값을 반환합니다.
- 이는 재귀 호출의 비효율성을 크게 줄여 줍니다.
시간 복잡도 개선:
- 메모이제이션을 사용하지 않는 순수 재귀 피보나치 함수의 시간 복잡도는 O(2^n)입니다.
- 하지만 메모이제이션을 사용하면, 각 숫자의 피보나치 값을 한 번만 계산하므로 시간 복잡도는 O(n)으로 감소합니다.
공간 복잡도:
- 메모이제이션은 추가 메모리를 사용합니다.
- 이 메모리는 각 계산된 결과를 저장하는 데 사용되며, n의 크기에 비례하여 증가합니다.
- 따라서 재귀의 스택 오버플로우 문제를 일으키지 않으면서도 효율적으로 문제를 해결할 수 있습니다.

- 재귀를 사용하지 않은 피보나치 수열을 구하는 코드

def fibonacci(n):
    if n <= 1:
        return n
    
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    
    return b

print(fibonacci(5))

장점:

효율성: 하위 문제의 결과를 저장하고 재사용함으로써 중복 계산 없이 문제를 해결하고, 시간 효율성을 향상시킵니다.
메모리 최적화: 반복문은 호출 스택을 사용하지 않으므로 재귀 함수에 비해 메모리 사용이 적고, 큰 입력 값에 대해서도 스택 오버플로우의 위험이 없습니다.

단점:

코드 복잡성: 문제의 수학적 또는 개념적 정의를 직접적으로 표현하기 어렵고, 반복문을 통한 접근은 때때로 코드의 복잡도를 증가시킬 수 있습니다.

어떤 방식이 더 나은가?

일반적인 사용성:
- 대부분의 실용적 프로그래밍 환경에서는 반복문을 사용한 피보나치 계산 방식이 더 효율적이며 권장됩니다.
- 이는 메모리와 실행 시간에서 더 효율적이기 때문입니다.
학습 및 교육적 목적:
- 코드의 간결성과 문제 해결 방식의 직관성을 위해 재귀를 사용할 수 있으나, 재귀의 메모리 사용과 실행 시간의 비효율성을 이해하는 것이 중요합니다.
- 또한, 재귀적 접근은 알고리즘 이해와 자료구조에 대한 근본적인 이해를 도울 수 있습니다.