순차·분기·반복·재귀

같은 일을 되풀이하는 두 가지 시선

가격이 2원·3원·4원인 상품의 합을 구하려면 0에서 시작해 2를 더하고, 그 결과에 3을 더하고, 다시 4를 더할 수 있다. ‘다음 가격을 지금 합계에 더한다’는 같은 동작을 되풀이하면 결과는 9원이다. 모든 가격을 더하는 일을 한꺼번에 상상하지 않고 지금 값과 다음 동작으로 나누는 것이 반복의 출발점이다.

다른 방법으로는 ‘1부터 3까지의 합은 1부터 2까지의 합에 3을 더한 것’이라고 생각할 수 있다. 더 작은 범위의 합을 구한 뒤 남은 덧셈을 마치는 방식이다. 이렇게 같은 형태의 작은 문제를 다시 부르는 재귀를 아래에서 한 줄씩 따라간다.

둘 다 순차·분기와 결합한다. 핵심은 횟수가 많다는 사실보다 매 단계 끝에 가까워지는가, 끝난 뒤 올바른 결과를 돌려주는가이다. 간단한 합계를 이해한 다음에 폴더 안의 폴더를 방문하는 예로 넓힌다.

먼저 되짚기: 반복은 흐름, 재귀는 함수 호출을 사용한다

제어흐름은 분기와 반복·호출로 다음 실행 위치를 정했고, 함수는 입력을 받아 결과를 만드는 처리단위였다. 반복은 흐름을 이전 지점으로 돌리고, 재귀는 함수가 더 작은 입력으로 자신을 호출한다. 두 방식 모두 종료조건이 필수다.

이미 배운 순차·분기·함수가 이어진다

순차는 준비·확인·처리를 정한 순서로 하는 것이고, 분기는 조건에 따라 다른 길을 고르는 것이다. 반복은 그림의 되돌아가는 경로를 사용한다. 재귀는 앞에서 배운 함수 호출을 이용해 더 작은 일을 요청한 뒤 그 결과로 남은 처리를 마친다. 어느 방법이든 ‘무엇을 기억하고 어디로 돌아가는지’를 확인해야 한다.

반복

반복은 종료조건까지 같은 규칙을 순차 적용하는 실행구조다. 반복마다 입력의 다음 항목으로 이동하거나 남은 양을 줄이는 진행이 있고, 지금까지 처리한 결과가 올바르다는 불변조건이 유지되어야 한다.

예를 들어 1·2·3을 더할 때 현재 합은 0 → 1 → 3 → 6으로 바뀐다. 합을 매번 0으로 다시 만들지 않고 직전 결과에 다음 수를 더한다. 여기서 계속 유지되는 관계는 ‘현재 합은 이미 더한 수들의 합’이며, 합계의 숫자 자체가 고정되어 있다는 뜻은 아니다.

재귀

재귀(recursion)는 문제를 더 작은 같은 형태의 문제와 종료사례로 정의하는 방법이다. 종료사례는 더 나누지 않고 바로 답을 주고, 재귀사례는 더 작은 문제의 결과로 현재 문제의 답을 만든다. 단지 자기 이름을 다시 부르는 것만으로는 종료가 보장되지 않는다.

1부터 3까지 더하는 일을 맡은 호출은 ‘1부터 2까지의 합이 돌아오면 3을 더한다’는 남은 일을 기억해야 한다. 그 작은 호출도 ‘1까지의 합이 돌아오면 2를 더한다’를 기억한다. 아래 교육 모형에서는 이처럼 호출별 입력·남은 일·돌아갈 위치를 저장한다. 마지막에 시작한 호출의 답부터 돌아오는 저장 구조를 호출 스택이라고 부르며, 구체적인 쌓임과 해제는 다음 계산에서 확인한다.

1부터 n까지 더하는 두 표현

n은 마지막에 더할 수를 뜻한다. 이 예의 허용 입력은 0 이상의 정수이고, n=0의 합은 더할 수가 없는 빈 합으로 0이다. 음수·소수·문자열은 입력 오류다. 계산은 정확한 정수 연산을 가정하며, 실제 프로그램의 수 표현 범위와 자원 한계는 별도로 정해야 한다.

total은 현재 합, i는 이번에 더할 수다. total = total + i는 오른쪽의 현재 값 둘을 더해 왼쪽 이름의 새 값으로 저장한다. <=는 ‘작거나 같다’이고, 반환은 현재 호출을 끝내 결과를 돌려주는 동작이다.

반복합(n):
    n이 0 이상의 정수가 아니면 입력 오류 반환
    total = 0
    i = 1
    i <= n 동안:
        total = total + i
        i = i + 1
    total 반환

n=3일 때는 다음처럼 진행한다. 조건 확인은 덧셈 전에 하고, i의 증가는 덧셈 후에 한다.

조건을 확인할 때 ‘1부터 i-1까지의 합이 total에 있다’가 불변조건이다. 시작에는 i=1이므로 아직 더한 수가 없어 total=0이다. i를 더하고 다음 수로 이동하면 이 관계가 유지된다. 마지막에는 i=4여서 1부터 3까지의 합 6이 남는다. n=0이면 첫 조건 1 <= 0이 거짓이므로 덧셈 없이 0을 반환한다.

이번에는 같은 합을 작은 호출로 나눈다.

재귀합(n):
    n이 0 이상의 정수가 아니면 입력 오류 반환
    n이 0이면 0 반환
    작은합 = 재귀합(n-1)
    n + 작은합 반환

작은합은 요청을 보내자마자 생기는 값이 아니다. 작은 호출이 끝나 결과를 돌려줄 때까지 현재 호출의 마지막 덧셈은 기다린다.

재귀합(3): 3 + 재귀합(2)의 결과를 기다림
  재귀합(2): 2 + 재귀합(1)의 결과를 기다림
    재귀합(1): 1 + 재귀합(0)의 결과를 기다림
      재귀합(0): 0 반환
    재귀합(1): 1 + 0 = 1 반환
  재귀합(2): 2 + 1 = 3 반환
재귀합(3): 3 + 3 = 6 반환

아래로 내려갈 때 n은 3·2·1·0으로 줄고, 돌아올 때 결과는 0·1·3·6이 된다. n이 0 이상의 정수이므로 1씩 줄이면 반드시 0에 도달한다. 음수 n=-1을 검사 없이 허용하면 -2·-3으로 멀어져 0에 도달하지 못하므로, ‘매번 1을 뺀다’만으로 종료를 설명하면 틀린다.

이 모형에서 n=3의 재귀는 n=0 호출까지 최대 4개의 호출 기록을 동시에 남긴다. 반복은 total·i 등 일정한 개수의 상태로 덧셈 3회를 한다. 같은 결과 6이 나온다고 기억하는 정보의 양까지 같지는 않다. 실제 실행환경이 특정 호출을 없애는 최적화를 제공하는지는 별도이며, 이 예에는 그러한 최적화를 가정하지 않는다.

IR-1: 작은 폴더 구조를 호출과 대기 목록으로 따라간다

이 예의 A, B, C, D는 폴더 이름이다. A 바로 안에 B와 D가 있고 B 안에 C가 있다. 선은 ‘바로 안에 있다’를 나타내며 왼쪽부터 방문한다. 시작 폴더 A를 root(루트), 바로 안의 폴더를 child(자식), 이런 포함 관계를 디렉터리 트리라고 부르는 표현을 아래 문제에서 사용한다. 자료구조의 일반 정의·비교는 다음 절에서 다루며 여기서는 이 네 폴더의 방문·복귀 동작을 먼저 읽는다.

visit(X)는 X를 방문하는 함수 이름이다. 현재 폴더 이름을 기록하고, 첫 자식 안을 끝까지 방문한 다음 다음 자식으로 간다고 정한다. 그래서 순서는 A→B→C→D다. 이렇게 한 갈래 안으로 먼저 들어가는 순서를 깊이우선이라고 읽는다.

visit(현재 폴더):
    현재 폴더 이름 기록
    각 자식을 왼쪽부터 차례로:
        visit(자식)
    반환

재귀 방식은 visit(A) → visit(B) → visit(C) → 반환 → 반환 → visit(D)처럼 호출스택에 돌아올 위치를 저장한다. C에서 돌아오면 B에는 더 볼 자식이 없어서 다시 A로 돌아간다. A는 ‘B 다음에는 D를 방문한다’는 위치를 기억하고 있었으므로 D로 이어간다. 마지막에는 D와 A의 호출도 차례로 반환해 끝난다.

최대 호출 깊이는 A-B-C의 3이다. 방문 이름을 4개 기록했다는 사실과 동시에 남아 있는 호출이 최대 3개라는 사실을 구분한다.

같은 순서를 반복으로 만들기

호출에 맡기던 다음 일을 직접 적어 둘 수도 있다. 아래의 대기는 맨 오른쪽에 넣고 맨 오른쪽에서 꺼내는 목록이다. ‘넣기’를 push, ‘꺼내기’를 pop이라고 쓰기도 한다. 이처럼 마지막에 넣은 것을 먼저 처리하는 명시적 스택을 사용하되, 지금은 별도 구현법을 외우기보다 표에서 실제 값을 움직여 본다.

대기 = [A]
대기가 비어 있지 않은 동안:
    현재 = 대기의 맨 오른쪽 항목을 꺼냄
    현재 이름 기록
    현재의 자식을 오른쪽부터 왼쪽으로 대기의 끝에 넣음

A 뒤에 B를 먼저 꺼내려면 D를 먼저 넣고 B를 나중에 넣어야 한다. 자식을 B·D 순서대로 넣으면 D가 먼저 나와 A→D→B→C가 된다. 이 차이는 재귀와 반복의 정답 차이가 아니라 약속한 방문순서를 구현하는 방법의 차이다.

이 네 폴더 예에서 명시적 대기는 최대 2개다. 호출 기록 3개와 다른 수이며, 전체 방문 결과를 목록으로 보관하면 별도로 4개를 저장한다. ‘반복이므로 추가 메모리가 언제나 일정하다’고 일반화하지 않는다. 자식이 하나씩인 긴 경로에서는 대기 1개로 진행할 수 있지만, A 아래에 100,000개의 자식을 한꺼번에 넣으면 대기 100,000개가 필요하다.

실제 디렉터리 문제로 바꿀 때의 계약

앞 예는 유한하고 처리 중 바뀌지 않으며, 다른 폴더로 되돌아가는 링크가 없는 포함 구조다. 실제 파일시스템에서는 권한 오류·목록 변경·다른 폴더로 이어지는 링크가 있을 수 있다. 이 예를 그대로 모든 파일시스템의 안전한 순회라고 주장하지 않는다.

교육용 설계에서는 제공된 자식 순서를 지키고 링크는 따라가지 않는다. 이름을 하나 기록할 때마다 출력 쪽에 전달하며, 방문 결과를 모두 메모리에 모으지 않는다. 방문 수와 대기 항목 수의 상한은 각각 100,000으로 정한다. 대기에 자식을 넣기 전에 현재 대기 수 + 넣을 자식 수를 확인하고, 처리 전에 방문 한도를 확인한다.

교육용 입력에 시작 폴더 자체가 없는 경우는 빈 구조로 허용해 방문 목록을 비우고 정상 완료로 반환한다. 시작 폴더는 있다고 주어졌지만 권한 때문에 열지 못하는 경우는 다른 실패이며 빈 구조로 숨기지 않고 오류와 부분결과를 표시한다. 입력이 빈 것과 읽기 실패를 구별해야 아래 답안의 경계 결과를 스스로 정할 수 있다.

예를 들어 대기 한도를 1로 줄이면 A의 자식 B·D를 둘 다 넣을 수 없다. 일부만 넣고 성공했다고 하지 않고 A까지의 부분결과와 ‘대기 한도 초과’를 알리고 멈춘다. B의 자식을 읽는 중 권한 오류가 나도 누락을 숨기지 않고 그 지점의 부분결과·오류를 표시한다. 이 설계는 중단 뒤 자동으로 이어서 실행하는 기능을 약속하지 않는다.

고정된 유한 포함 구조에서는 한 항목이 한 번만 대기에 들어가고 한 번만 방문되므로 결국 끝난다. 링크를 따라가기로 바꾸면 이 전제가 깨질 수 있다. 이미 방문한 식별자를 기억해 다시 처리하지 않는 별도 규칙과 그 저장비용이 필요하며, 단순히 반복으로 바꾸는 것만으로 순환이 해결되지는 않는다.

어느 표현을 고를까

단순 합계에서는 반복을 택하면 일정한 개수의 상태로 진행 과정을 보여주기 쉽다. 반면 중첩된 폴더를 ‘현재 처리 후 자식에 같은 규칙 적용’으로 쓰면 재귀의 뜻이 잘 드러난다. 다만 수학적으로 끝난다는 것과 실제 실행환경의 호출 저장공간이 충분하다는 것은 다르다.

매우 깊은 경로에서는 명시적 대기를 쓰는 반복을 우선 검토하되, 넓은 구조에서 대기 목록이 커지는지도 확인한다. 두 방식의 전체 비용을 비교할 때 입력 보관·방문 결과 보관과 작업 상태를 섞지 않는다. 이 비교의 저장 개수는 특정 언어의 실제 바이트 사용량 측정값이 아니다.

실패조건과 방어

한 칸 어긋난 반복. 합계의 조건을 i < n으로 쓰면 n=3에서 1·2만 더해 3을 낸다. i <= n이어야 마지막 3까지 더해 6이다. 시작값·조건 확인·증가 시점을 상태표로 대조하고 n=0·1도 확인한다.

진행 없는 반복. i = i + 1을 빠뜨리면 같은 i를 계속 더한다. ‘참인 동안 반복’이라는 문장이 아니라 종료 쪽으로 움직이는 값이 실제로 있는지 확인한다.

입력 경계 없는 재귀. 종료사례가 0이어도 음수나 소수 입력을 그대로 허용하면 0에 도달하지 않을 수 있다. 허용 입력 검사와 그 범위에서 작아지는 이유를 함께 적는다.

깊이·대기 폭증. 재귀는 깊은 경로에서 호출 한계에, 반복은 넓은 구조에서 대기 저장 한계에 걸릴 수 있다. 한도 초과 전에 멈추고 정상 완료와 부분결과를 구분한다.

중복 재귀 계산. 같은 하위 문제의 답을 여러 곳에서 요청하면 이미 구한 답을 다시 계산할 수 있다. 예를 들어 재귀합(2) + 재귀합(2)를 그대로 실행하면 같은 합을 두 번 구한다. 첫 결과를 기억해 다시 쓸지, 저장·조회에 드는 비용보다 재계산이 더 싼지 판단한다. 여기의 재귀합(n) 한 번은 매 단계 n-1을 한 번만 부르므로 두 갈래 중복은 없다.

자체 10점 문제

반복과 재귀를 비교하고 선택기준을 설명하시오.

요구어는 비교, 설명이다. 정의만 둘로 나누지 말고 같은 합계의 결과 6을 만드는 과정에서 종료·진행량·상태 위치가 어떻게 다른지 연결한다. 다음으로 폴더처럼 중첩된 문제에서는 왜 다른 표현이 자연스러운지, 깊이와 대기 크기를 왜 확인하는지 설명한다.

자체 25점 문제

깊은 디렉터리 트리를 순회하는 알고리즘을 반복과 재귀 관점에서 설계하고 실패경계를 제시하시오.

요구어는 설계, 제시다. 여기서 디렉터리는 폴더, root는 시작 폴더이며 IR-1의 포함 구조를 사용한다. 현재 이름을 먼저 기록한 뒤 자식 안을 왼쪽부터 끝까지 방문하는 순서를 지킨다.

재귀의 기본 절차를 먼저 설명하고, 깊은 입력에서 선택할 반복 절차와 상태를 구체화한다. 단순히 ‘스택을 사용한다’에서 끝내지 말고 넣는 순서·상한 검사 시점·오류 결과·부분결과의 의미를 보여준다.

출처와 적용 경계

합계와 네 폴더 예는 입력·호출·반환을 설명하는 자체 교육 모형이다. 호출을 없애는 최적화 없이 정확한 정수 연산을 가정했으며 실제 언어의 정수 범위·호출 한계·라이브러리 동작은 구현 사양으로 확인해야 한다. 실제 환경이 호출을 다른 형태로 최적화할 수 있다는 사실을 모든 재귀에 적용되는 보장으로 쓰지 않는다.

폴더 구조·자식 순서·방문/대기 100,000 상한은 교육용 가정이지 파일시스템의 공통 보장이 아니다. 자체 문제·답안과 유한 예제 검증은 공식 기출·공식 채점이나 실제 제품의 안전성 승인과 다르다.

30초 정리

1. 반복은 현재 상태와 다음 처리 위치를 바꾸며 불변조건을 유지하고 종료에 가까워져야 한다.
2. 재귀는 종료사례에 도달할 작은 문제를 호출하고, 돌아온 결과로 기다리던 처리를 마친다.
3. 결과뿐 아니라 허용 입력·호출 깊이·대기 크기·오류 결과를 비교하며 반복을 무조건 상수공간이라고 하지 않는다.

자기교정과 조건 변경

반복합(3)의 조건을 i<n으로 바꾸면? i=1·2에서만 더해 3을 반환한다. 원래 문제의 답 6이 아니며 마지막 항목을 빠뜨린 것이다. n=0·1에서도 결과를 다시 확인한다.

재귀합에 n=0 또는 n=-1을 주면? 0은 종료사례여서 0을 반환하고 -1은 호출을 더 하기 전에 입력 오류로 끝난다. 둘을 같은 빈 합으로 처리하면 허용 입력의 의미가 바뀐다.

C를 B 안이 아니라 A 안의 마지막 자식으로 옮기면? A의 자식 순서가 B·D·C이므로 방문은 A→B→D→C다. 깊이는 2가 되지만 반복 대기는 A 처리 뒤 [C,D,B]의 3개가 되어, 깊이 감소가 대기량 감소를 뜻하지 않는다.

깊이우선 대신 같은 층부터 방문하면? A 다음에 바로 안의 B·D를 먼저 보고 그다음 C를 본다. 방문순서는 A→B→D→C이며, 먼저 넣은 것을 먼저 꺼내는 큐의 적용은 다음 절에서 비교한다. 순서 요구가 바뀌었으므로 원래 깊이우선 답을 그대로 정답으로 남기지 않는다.

같은 하위문제 결과가 반복해서 필요하면? 어느 입력의 답을 몇 번 다시 구하는지 그려 본다. 재사용할 답과 저장비용을 먼저 정하고, 모든 재귀에 중복이 있다고 단정하지 않는다.