[자료구조/알고리즘 이론] 반복문과 재귀

반복문과 재귀 모두 특정 작업을 반복 수행하는 프로그래밍 기법이다. 두 가지 방식에 어떤 차이점이 있는지, 또 장단점은 어떤 것이 있는지 알아보자.

 

반복문

말 그대로 특정 작업을 반복하는 기법입니다. 특정 조건을 만족할 때까지 코드 블럭을 반복하는 작업을 수행합니다. 반복문은 주로 for과 while을 사용하여 나타냅니다.

 

파이썬에서의 반복문

for문을 사용한 반복문입니다.

- for i in data 의 경우 자료형에 포함된 요소를 바로 iteration을 통해 불러옵니다. 

- for i in range(start, end) 의 경우 주어진 숫자 범위 내에서 iteration을 수행합니다.

numbers = [1,2,3,4,5]

for i in numbers:
    print(i)
    
for i in range(len(numbers)):
    print(numbers[i])

 

while을 사용한 반복문입니다.

- 특정 조건을 만족할 때까지 반복 작업을 수행합니다.

- while(True) 설정을 통해 일단 반복문을 수행하고, 코드블럭 내부에서 if(condition) break 를 통해 루프를 끝낼 수도 있습니다.

condition = 5
cnt = 0

# 방법 1
while cnt < condition:
    print(cnt) 
    cnt += 1
    
print('종료')

# 방법 2
while True:
    print(cnt) 
    cnt += 1
    if cnt >= condition:
        break
    
print('종료')

 

자바에서의 반복문

자바에서도 마찬가지로 for, while을 통해 반복 작업을 수행할 수 있습니다.

 

for을 사용한 반복문입니다.

- for each loop를 사용해서 자료형의 요소에 바로 접근할 수 있습니다.

- 인덱스를 사용하여 주어진 범위 내에서 반복 작업 수행이 가능합니다.

int[] numbers = {1,2,3,4,5};

// for-each loop
for(int i : numbers) {
    System.out.println(i);
}

// for loop
for(int i = 0; i < numbers.length; i++) {
    System.out.println(numbers[i]);
}

 

while을 사용한 반복문입니다. 앞서 설명한 파이썬에서의 두 가지 방식 모두 사용가능합니다.

int cnt = 0;
int condition = 5;

while(cnt < condition) {
    System.out.println("cnt = " + cnt);
    cnt++;
}
System.out.println("종료");

while(true) {
    System.out.println("cnt = " + cnt);
    cnt++;
    if(cnt >= condition) {
        break;
    }
}
System.out.println("종료");

 

재귀

인터넷 찾아보면 웃긴 짤이 많다

재귀는 함수가 자기 자신을 호출하는 프로그래밍 기법입니다. 주로 복잡한 문제를 하위 문제로 나누어서 해결할 때 사용합니다. 우리가 흔히 아는 팩토리얼, 피보나치 수열이 재귀로 해결이 가능한 대표적인 문제들이다. 재귀 함수는 자기 자신을 계속 호출하기 때문에 종료 condition을 설정하여 해당 condition을 만족할 경우 재귀 함수를 종료시켜주어야 합니다.

 

팩토리얼

기본적인 로직은 동일하므로 파이썬으로 진행하겠습니다.

재귀를 이용한 팩토리얼 계산입니다.

def factorial(n):
    # n이 0이되면 1을 리턴합니다. 0! = 1
    if n == 0:
        return 1
    return n * factorial(n - 1)

print(factorial(3)) # 6

 

피보나치 수열

재귀를 이용한 피보나치 수열입니다. fibonacci(0) = 0, fibonacci(1) = 1 로 가정하고 진행합니다.

def fibonacci(n):
    if(n == 0):
        return 0
    elif(n == 1):
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)
    
print(fibonacci(10)) # 55

 

반복문 vs 재귀

1. 구조

- 반복문: 명확하게 시작, 조건, 종료 및 증감을 나타내어 코드를 읽는 사람 입장에서 직관적이기에 이해하기가 더 쉽습니다. 또한 성능면에서 재귀보다 더 뛰어납니다.

- 재귀: 함수가 자기 자신을 호출하여 문제를 하위 문제로 쪼개어 해결합니다.

 

2. 사용 사례

- 반복문: 반복이 명확하고 종료 조건이 쉽게 정의될 수 있을 때 사용합니다.

- 재귀: 문제를 동일한 유형의 하위 문제로 나눌 수 있을 때 사용합니다.

 

3. 메모리 사용

- 반복문: 메모리 사용이 효율적이며 스택 오버플로우가 발생하지 않습니다.

- 재귀: 각 함수 호출이 호출 스택에 추가되므로 재귀 호출이 깊어질 경우 스택 오버플로우가 발생할 수 있습니다.

 

4. 전체적인 성능

- 반복문: 일반적으로 재귀보다 빠르고 메모리 사용이 적습니다.

- 재귀: 단순한 문제를 해결할 때 코드가 더 간결할 수 있지만, 이해와 디버깅이 복잡할 수 있습니다.

 

반복문이 더 효율적인 이유?

반복문이 더 효율적인 이유는 크게 3가지로 나뉩니다.

 

1. 메모리 사용 효율성: 루프문 코드 블럭 내의 임시 변수는 CPU 레지스터 혹은 스택의 고정된 작은 공간만을 사용합니다.

2. 함수 호출 오버헤드: 함수를 호출하기 위해 필요한 간접적인 시간/메모리가 재귀 횟수만큼 늘어납니다.

3. 스택 오버플로우 위험: 반복문은 무한 루프를 제외하고는 스택 오버플로우의 위험이 없습니다.

 

앞서 설명한 것처럼 반복문과 재귀에서는 메모리 사용 측면에서 본질적인 차이가 있습니다. 반복문인 for과 while문 수행 시에는 CPU가 직접 반복 연산을 관리합니다. 그렇기 때문에 실행되는 동안 메모리를 거의 추가적으로 사용하지 않습니다.

 

for문을 통해 연산작업을 수행한다고 할 때, CPU 레지스터가 직접 함수를 관리합니다.

+-----------------------------------------+
|           반복문 메모리 구조            |
+-----------------------------------------+
|   변수(total, i)      | CPU 레지스터   |
+-----------------------------------------+

 

반면 재귀함수를 사용할 경우 함수가 종료 조건을 달성할 때까지 자기 자신을 계속 호출하게 됩니다. 함수를 1번만 호출하는 반복문과는 다르게 함수를 n번 호출하게 됩니다. 각 함수가 호출될 때마다 새로운 함수 호출 스택을 사용하기 때문에 재귀가 깊어질 경우에 스택 오버 플로우가 발생하게 됩니다.

+-----------------------------------------+
|            재귀 메모리 구조                 |
+-----------------------------------------+
| sum_to_n(5)       | 5 + sum_to_n(4)     |
+-----------------------------------------+
| sum_to_n(4)       | 4 + sum_to_n(3)     |
+-----------------------------------------+
| sum_to_n(3)       | 3 + sum_to_n(2)     |
+-----------------------------------------+
| sum_to_n(2)       | 2 + sum_to_n(1)     |
+-----------------------------------------+
| sum_to_n(1)       | 1                   |
+-----------------------------------------+

 

그럼에도 재귀를 사용하는 이유

그럼 재귀 왜 씀? 걍 무조건 반복문 쓰면 되는 거 아님? 이라고 생각할 수 있지만.. 특정 문제를 해결할 때 재귀가 더 효율적, 직관적, 간결할 수 있습니다. 이제부터 설명할 트리 탐색의 경우가 그렇습니다.

 

아래와 같은 트리가 있고 모든 노드를 방문해야 한다고 생각해봅시다.

            A
           / \
          B   C					트리입니다.
         / \   \
        D   E   F

 

재귀를 사용할 경우 코드가 굉장히 직관적이고 짧습니다.

def visit(node):
    if node is not None:
        visit(left_node)
        visit(right_node)

visit(A)

 

 

은탄환은 없다라는 말이 있듯이 정답은 없기 때문에 상황마다 본인이 필요한 방법으로 접근하는 것이 정답입니다.