Recursion vs. Iteration

Iteration과 Recursion은 프로그래밍에서 반복적인 작업을 수행하는 두 가지 주요 방식이다.

Iteration은 루프를 사용하여 특정 조건이 만족될 때까지 코드 블록을 반복 실행하는 방식이다.
주로 for, while 등의 루프 구조를 사용한다.
Iteration은 명시적인 반복 구조를 가지며, 각 반복마다 변수의 상태가 변경된다.

Recursion은 함수가 자기 자신을 호출하여 문제를 해결하는 방식이다.
복잡한 문제를 더 작고 간단한 문제로 나누어 해결한다.
Recursion은 base case(종료 조건)와 recursive case(재귀 호출)로 구성된다.

Iteration vs. Recursion

특성IterationRecursion
정의루프를 사용한 반복 실행함수가 자기 자신을 호출
제어 구조루프 (for, while 등)함수 호출 스택
종료 조건루프 조건이 거짓이 될 때Base case에 도달할 때
메모리 사용일반적으로 적음함수 호출 스택으로 인해 많음
속도대체로 빠름대체로 느림 (오버헤드 존재)
코드 복잡성간단한 문제에 적합복잡한 문제 해결에 유용
무한 반복 위험루프 조건 오류 시 발생Base case 누락 시 발생
문제 해결 접근순차적 실행분할 정복
가독성단순한 경우 높음복잡한 경우 높음
디버깅상대적으로 쉬움상대적으로 어려움

두 방식 모두 장단점이 있으며, 문제의 특성과 요구사항에 따라 적절한 방식을 선택해야 한다.
Iteration은 단순하고 반복적인 작업에 적합하며, Recursion은 복잡한 문제를 분할하여 해결하는 데 유용하다.

예시를 통한 비교

피보나치 수열을 구하는 알고리즘을 통한 두 가지 방식의 구현:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

def fibonacci_iterative(n):
    # 반복적 방식으로 피보나치 수열의 n번째 값을 계산
    if n <= 1:
        return n
    
    # 이전 두 수를 저장할 변수 초기화
    prev = 0
    current = 1
    
    # n-1번 반복하면서 다음 피보나치 수를 계산
    for _ in range(n - 1):
        prev, current = current, prev + current
    
    return current

def fibonacci_recursive(n):
    # 재귀적 방식으로 피보나치 수열의 n번째 값을 계산
    # 기저 조건
    if n <= 1:
        return n
    # 재귀 단계: f(n) = f(n-1) + f(n-2)
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

# 실행 예시
n = 5
print(f"Iterative result: {fibonacci_iterative(n)}")  # 5
print(f"Recursive result: {fibonacci_recursive(n)}")  # 5

참고 및 출처