반복은 프로그래밍 언어의 기본 조건이다
프로그래밍 언어의 최소 조건 중 하나는 조건문과 반복문의 존재이다.
이 중 반복문은 어셈블리 수준으로 내려가지 않는 한, 크게 두 가지 메커니즘 중 하나를 지원한다.
- 첫 번째는
for문을 이용한 반복(iteration) - 두 번째는 재귀(recursion)
일반적인 경험에 비추어 볼 때, 재귀만 제공하는 언어는 보편적이라고 하긴 어렵고, 함수형 프로그래밍에 특화된 언어에서 주로 볼 수 있다. 그 중에서는 아예 문법적으로 for문이 존재하지 않는(…) 경우도 존재한다.
이 글에서는 “반복”을 repeatation(반복 자체)으로, 반복을 구현하기 위한 방법으로서의 반복은 iteration으로 표기한다.
두 용어가 명시적으로 구분될 필요가 있는 경우에는 영문 표기를 병기한다.
반복과 재귀의 구현: 어셈블리 관점에서 보기
어셈블리 수준에서 반복은 어떻게 구현되는가?
저수준의 이해를 돕기 위해, 어셈블리에서 반복을 구현한 방법을 state machine 관점으로 살펴보자. 필자가 생각할 수 있는 가장 저수준 단계인 언어인 어셈블리에서는 반복을 구현하기 위해 다음 두 가지 방법을 사용한다:
1. goto와 label을 이용한 방법
- 프로그램 코드의 특정 위치에 이름을 붙이고(
label) - 두 값을 비교하는
cmp명령어를 통해 컨트롤 레지스터(ZF: zero flag)를 설정 - 해당 플래그에 기반하여
jmp계열 명령어로 분기 처리
이 방식은 조건 처리 후 빠져나오는 역할을 하는 명령어가 반드시 필요하며 (없으면 무한 루프),
비교하는 값을 state로 가지는 상태 기계(state machine)로 볼 수 있다.
2. loop {label}을 이용한 방식
- 반복할 횟수를
ecx레지스터에 설정하고 - 아래에
label을 붙인 다음loop {label}형태로 반복을 구성
이 방식은 라벨부터 loop까지의 블럭이 반복되며, ecx의 값이 0이 되면 종료된다.
ecx 값을 state로 갖는 상태 기계로 이해할 수 있다.
반복과 재귀
jmp와 label을 이용한 반복은 재귀에 가깝고,
ecx 레지스터 값을 이용한 반복은 C언어의 기본적인 for문에 가깝다.
하지만 어차피 반복도 재귀도 내부적으로는 상태(state)의 변화에 기반한 것이기 때문에,
궁극적으로는 둘 다 state machine으로 구현된다는 점에서 공통점을 가진다.
반복은 실제로 어디서 쓰이는가?
삼각형 출력이나 구구단처럼 단순한 예제가 아니라면,
현실에서 반복이 필요한 상황의 대부분은 collection 순회이다.
- 특정 배열이나 리스트를 순회
- DB에서 가져온 rows를 처리
- 파일 시스템의 특정 디렉토리 이하의 파일 목록을 순회 등
이런 경우, 반복 시 카운터의 값 자체보다 그 카운터로 접근하는 요소(element)가 훨씬 더 중요하다.
물론 여러 배열을 동시에 순회하거나, 정렬 알고리즘처럼 인덱스가 중요한 경우는 예외다.
그러나 현대 언어에서는 이런 특수 상황조차 언어 차원에서 iterator나 map 등의 기능으로 처리하게 되며,
결국 개발자가 반복의 핵심이 무엇인지 이해하는 것이 더 중요해진다.
반복의 기반이 되는 두 가지 Collection 구조
현대 언어에서 반복은 주로 collection을 대상으로 수행되며, 이 collection은 대체로 두 가지 형태로 나뉜다:
1. Array 기반 Collection
- 각 원소가 인접한 메모리에 저장됨
- O(1) 시간 복잡도로 인덱스 접근이 가능
- 성능상 이점 (cache locality)
이러한 구조는 대부분의 언어(C, C++, Java, Python, JavaScript 등)에서 기본적인 collection으로 채택된다.
대표적으로 ArrayList, vector, tuple, array 등이 이에 해당된다.
연속된 block 단위로 메모리를 읽는 CPU의 특성 덕분에 성능이 좋음
인덱스 계산은 base address + (unit size × index)로 접근
2. Linked List 기반 Collection
- 각 원소가 서로 다른 메모리에 저장되고, next pointer로 연결됨
- 접근 시간은 O(n)이지만, 지연성(laziness)과 무한 데이터 표현에서 유리
- 함수형 언어(Haskell, Clojure, F# 등)에서 자주 사용
linked list의 강점 중 하나는 무한 리스트를 다룰 수 있다는 것이다.
실제 메모리에 모든 데이터를 올릴 필요 없이, 필요할 때마다 한 원소씩 생성하면 된다.
또한 하나의 원소(head)가 전체 리스트를 대표할 수 있는 구조이기도 하다.
이 때문에 함수형 언어에서는
x:xs,(cons 69 (cons 613 nil))같은 형태가 자연스럽다.
이터레이션과 지연 평가
이터레이션이 가진 강점 중 하나는 지연 평가(lazy evaluation)와의 궁합이다.
이터레이션에서는 현재 상태를 기반으로 다음 값을 정의할 수 있기 때문에,
모든 데이터를 한꺼번에 메모리에 올릴 필요 없이, 순차적으로 계산해 나갈 수 있다.
언어별 이터레이션 구현 방식 예시
- Python:
__next__메서드 - C++:
operator++오버로딩 - JavaScript, Python, Java:
generator,yield키워드
재귀의 내부 동작과 한계
재귀는 함수가 자기 자신을 호출하는 구조로,
각 호출마다 새로운 스택 프레임이 생성된다.
재귀의 비용
- 새로운 frame 생성
- 함수의 지역변수 및 파라미터 복사
- 메모리 할당 (stack 공간)
- 시스템 콜을 통한 메모리 접근
이러한 이유로 대부분의 언어에서는 재귀 깊이에 제한을 둔다.
꼬리 재귀 최적화 (Tail Call Optimization)
꼬리 위치(tail position)에 위치한 재귀 호출은,
새로운 스택 프레임을 만들지 않고, 기존 frame을 재사용하는 방식으로 최적화 가능하다.
언어별 지원 여부:
- Python: 미지원
- Java:
Function등 제한적 - Kotlin:
tailrec키워드 - JavaScript: ES6 이후 일부 지원
재귀와 반복의 이론적 동등성
이론적으로, 재귀와 이터레이션은 동등하다.
- 반복으로 구현 가능한 모든 코드는 재귀로 구현 가능
- 반대로 재귀로 구현된 코드도 반복으로 바꿀 수 있음
따라서 재귀를 지원하지 않는 언어에서도 상태 기계를 직접 구현해 반복을 흉내낼 수 있다.
예를 들어:
- 상태값 하나만 필요한 경우 →
while문 기반 구현 - 복수 상태가 필요한 경우 →
stack기반의 순회 로직
마무리: 반복과 재귀, 그리고 구조에 대한 이해
반복(repeatation)의 구현으로써의 이터레이션과 재귀, 그리고 이를 뒷받침하는 collection 구조에 대한 이해는
프로그래밍 언어 자체를 이해하는 데 큰 도움이 된다.