[알고리즘] 재귀(Recursion)

ChaeHyeong·2024년 8월 19일

개념 알고리즘 재귀 팩토리얼

알고리즘 & 자료구조

목록 보기

2/6

재귀(Recursion-Basic)

"출처: https://www.linkedin.com/pulse/recursion-explained-understand-you-must-first-ignacio-chitnisky"

1. Recursion란?

재귀(Recursion)는 함수가 자기 자신을 호출하는 프로그래밍 기법입니다.
문제를 더 작은 하위 문제로 나누어 해결하는 데 유용하며, 수학적 정의나 알고리즘에서 반복적으로 사용하는 방식입니다.
재귀함수(Recursion Function)는 의미 그대로 자기 자신을 호출하는 함수

2. Recursion Function 조건

재귀 함수가 올바르게 작동하기 위해서는 기본적으로 아래 두 가지 수행 조건을 만족해야 합니다

기저 사례(Base Case)
- 재귀 호출을 멈추는 조건입니다.
- 기저 사례가 없으면 재귀 함수는 무한히 자기 자신을 호출해 프로그램이 종료되지 않습니다.
재귀 단계(Recursive Case)
- 함수가 자기 자신을 호출하여 문제를 더 작은 하위 문제로 나누는 단계입니다.
- 기저 사례에 도달할 때까지 계속해서 호출됩니다.
- 문제를 점점 더 작은 하위 문제로 나누어 결국 기저 사례에 도달하는 것이 재귀 함수의 핵심입니다.

3. 재귀의 대표 예시 - 팩토리얼

재귀 함수를 이용하는 대표적인 예제는 팩토리얼 문제이다.
팩토리얼은 양의 정수 n에 대해 n부터 1까지의 모든 정수를 곱한 값을 의미한다.
수학적으로 n! = 1 2 3 … (n-1) * n로 정의된다(단, 0!와 1!는 1로 정의된다)

- 예시: 5!를 출력해라

def factorial(n):
    if n <= 1:  # 기저 사례: n이 1 이하일 경우, 재귀 호출을 멈추고 1을 반환
        return 1    # 0!와 1!는 1로 정의되어 있음
    else:  # 재귀 단계: n이 1보다 클 경우
        return n * factorial(n - 1) # n을 n-1의 팩토리얼과 곱하여 계산

print(factorial(5))  # 5!를 계산하여 출력 (결과: 120)

1. 재귀 함수를 사용한 팩토리얼 계산

기저 사례(Base Case)
- n ≤ 1인 경우, 더 이상 재귀 호출을 하지 않고 1를 반환한다.
- 재귀 호출이 끄나는 조건으로, 0!와 1!는 1로 정의되어 있다
재귀 단계(Recursive Case)
- n > 1인 경우, factorial(n)은 n * factorial(n - 1)로 계산됩니다.
- 이 과정에서 함수는 자기 자신을 호출하며, n이 점점 작아져서 결국 기저 사례에 도달합니다

2. 재귀 함수의 동작 과정

[Step]

Step 1: factorial(5) 호출. n이 5이므로 5 * factorial(4)를 반환합니다.
Step 2: factorial(4) 호출. n이 4이므로 4 * factorial(3)를 반환합니다.
Step 3: factorial(3) 호출. n이 3이므로 3 * factorial(2)를 반환합니다.
Step 4: factorial(2) 호출. n이 2이므로 2 * factorial(1)를 반환합니다.
Step 5: factorial(1) 호출. n이 1이므로 기저 사례에 해당하고, 1을 반환합니다.

[함수 호출 역순 return]

factorial(2)는 2 * 1 = 2를 반환합니다.
factorial(3)는 3 * 2 = 6을 반환합니다.
factorial(4)는 4 * 6 = 24를 반환합니다.
factorial(5)는 5 * 24 = 120을 반환합니다.

최종적으로 print(factorial(5))는 120을 출력합니다.

4. 재귀 함수의 장점, 단점 및 유의 사항

재귀 함수는 특정 문제를 간결하고 직관적으로 해결할 수 있는 도구입니다.

하지만 그만큼 주의할 점도 많습니다.

아래에 재귀 함수의 장점과 단점을 살펴보고, 재귀 함수 사용 시 유의사항을 정리해 보겠습니다.

4-1. 재귀 함수의 장점

코드의 간결성
- 재귀 함수는 문제를 더 작은 하위 문제로 나누어 해결하는 방식이므로, 복잡한 문제를 단순하고 간결하게 표현 할 수 있습니다.
- 특히 수학적 정의가 재귀적 구조를 띠는 경우, 이를 프로그래밍으로 구현할 때 재귀 함수를 사용하면 수학적 정의를 그대로 반영할 수 있습니다.
문제 분할에 유리
- 재귀 함수는 분할 정복(Devide and Conquer) 전략과 밀접한 관련이 있습니다.
- 큰 문제를 더 작은 문제로 나누고, 그 하위 문제를 해결하는 방식이 자연스럽게 재귀 함수의 구조와 일치합니다.
- 이 때문에, 퀵소트(Quick Sort), 병합 정렬(Merge Sort), 이진 탐색(Binary Search) 등에서 재귀 함수가 유용하게 사용됩니다.
데이터 구조 탐색에 적합
- 재귀 함수는 트리(Tree) 또는 그래프(Graph) 구조를 탐색할 때 특히 유용합니다.
- 트리 구조에서 각 노드를 탐색할 때, 재귀적으로 자식 노드를 방문하는 방식은 코드의 가독성을 높이고, 복잡한 로직을 단순하게 구현할 수 있게 됩니다.
- 예를 들어, 트리의 깊이 우선 탐색(DFS)은 재귀적으로 구현하기에 매우 적합한 알고리즘 입니다.

4-2. 재귀 함수의 단점

성능 문제
- 재귀 함수는 함수 호출 스택을 사용하기 때문에, 함수 호출이 많아질수록 성능이 저하될 수 있습니다.
- 특히, 중복된 연산이 많을 경우 불필요한 함수 호출이 반복되며 성능에 큰 영향을 미칠 수 있습니다.
스택 오버플로우(Stack Overflow) 위험
- 재귀 함수는 함수 호출 스택에 각 호출이 쌓이기 때문에, 재귀 호출이 너무 깊어지면 스택 오버플로우가 발생할 수 있습니다.
- 특히 재귀 호출이 많이 필요한 문제를 다룰 때는 주의가 필요합니다.

4-3. 재귀 함수 사용 시 유의사항

기저 사례(Base Case) 명확히 정의
- 재귀 함수 사용 시 가장 중요한 것은 기저 사례(Base Case)를 명확하게 정의한느 것입니다.
- 기저 사례가 제대로 정의되지 않으면 재귀 함수는 무한히 자기 자신을 호출하게 되어 프로그램이 종료되지 않거나 스택 오버플로우가 발생할 수 있습니다.
- 따라서, 재귀 함수 작성 시 반드시 재귀 호출을 멈출 조건을 정확하게 설정해야 합니다.
메모이제이션(Memoization) 및 동적 프로그래밍(Dynamic Programming)
- 성능 문제를 해결하기 위해 메모이제이션(Memoization) 또는 동적 프로그래밍(Dynamic Programming) 기법을 사용하면 재귀 함수의 효율을 높일 수 있습니다.
- 이는 중복된 계산을 저장해두고, 동일한 하위 문제를 반복적으로 계산하지 않도록 하는 방법입니다.