요약

자기 자신을 다시 부르는 프로시저다. 러시아 인형을 열면 조금 작은 인형이 나오고, 그것을 또 열다가 더 열 수 없는 가장 작은 인형에서 멈춘 뒤, 연 순서의 거꾸로 하나씩 닫아 나오는 것과 같다. 부를 때마다 스택에 그 호출만의 칸이 새로 쌓여서, 같은 코드를 돌려 쓰면서도 호출마다 자기 값을 따로 기억한다. 대신 깊이 들어갈수록 스택을 그만큼 먹고, 멈추는 조건이 없으면 스택이 바닥나 프로그램이 죽는다.

예시로 보기

5! = 5 × 4!이고 4! = 4 × 3!이다. 같은 모양이 작아지며 되풀이된다. 이런 계산을 반복문으로 바꾸려면 식을 다시 짜야 하지만, 프로시저가 자기를 부를 수 있으면 식 그대로 옮기면 된다. 문제는 하나다. 프로시저의 코드는 한 벌뿐인데, 5를 든 호출과 4를 든 호출이 동시에 살아 있어야 한다. 그 값들을 어디에 따로 둘 것인가.

먼저 값을 레지스터에만 두는 쉬운 예다. CalcSum은 ECX에 든 수부터 1까지를 EAX에 더한다.

CalcSum PROC
    cmp  ecx,0          ; 남은 수가 0인가?
    jz   L2             ; 그러면 그만둔다
    add  eax,ecx        ; 아니면 합에 더하고
    dec  ecx            ; 하나 줄여서
    call CalcSum        ; 자기를 다시 부른다
L2: ret
CalcSum ENDP

main이 EAX = 0, ECX = 5로 부르면 call이 실행될 때마다 스택에 복귀 주소가 하나씩 쌓인다. L1은 main에서 call 다음 줄의 주소, L2는 CalcSum 안에서 call 다음 줄(ret)의 주소다.

스택에 넣은 복귀 주소 그때의 ECX 그때의 EAX
L1 5 0
L2 4 5
L2 3 9
L2 2 12
L2 1 14
L2 0 15

여섯 번째 호출에서 ECX가 0이라 ret으로 돌아간다. 돌아간 곳은 L2, 곧 또 ret이다. ret이 여섯 번 이어지며 복귀 주소 여섯 개(24바이트)를 차례로 꺼내고 main으로 돌아온다. EAX = 15다. CalcSum은 메모리를 한 번도 읽지 않고 ECX 자신을 더할 뿐이다. 그래서 ECX = \(n\)으로 부르면 \(n + (n-1) + \cdots + 1 = n(n+1)/2\)를 구한다1.

검증: CalcSum의 표 여섯 줄과 ECX = 0~59에서 결과가 \(n(n+1)/2\)인 것, Factorial(0)~(12)가 \(n!\)과 같은 것, 12!을 부를 때의 앞쪽 프레임 네 개, Factorial(3)의 프레임 주소와 곱하는 순서, 호출마다 12바이트, 13!에서 넘치는 것 — 47_recursive-procedure_impl.py (실제 어셈블러가 아니라 파이썬 흉내로 확인)

정의

재귀는 프로시저가 자기 자신을 부를 때, 또는 프로시저 A가 B를 부르고 B가 다시 A를 부를 때 생긴다. 프로시저를 점으로, 호출을 화살표로 그리면 재귀는 한 바퀴 돌아 제자리로 오는 고리(cycle)를 만든다.

재귀 프로시저에는 두 갈래가 있어야 한다1.

  • 바닥 조건(base case): 자기를 부르지 않고 바로 답을 내는 경우. CalcSum의 ECX = 0, 아래 Factorial의 \(n = 0\).
  • 재귀 단계: 문제를 더 작게 만들어 자기를 부르는 경우. 부를 때마다 바닥에 가까워져야 한다.

Factorial

\(n\)의 계승 \(n!\)은 1부터 \(n\)까지를 모두 곱한 수이고, \(0! = 1\)로 약속한다. C로 쓰면 이렇다.

int factorial(int n)
{
    if (n == 0)
        return 1;
    else
        return n * factorial(n - 1);
}

CalcSum과 다른 점이 있다. 자기를 부르고 돌아온 다음에 할 일(n *)이 남아 있다. 그래서 돌아왔을 때 자기의 \(n\)을 기억하고 있어야 한다. 호출마다 \(n\)을 스택 프레임에 따로 두는 까닭이다.

입력과 출력. 부르는 쪽이 \(n\)(부호 없는 32비트 수)을 스택에 넣고 부른다. 돌아오면 EAX에 \(n!\)이 있고, 넣었던 \(n\)은 프로시저가 치웠다. \(n!\)이 32비트에 들어가야 맞는 값이 나온다(\(n \le 12\))1. 코드는 이렇다.

Factorial PROC
    push ebp
    mov  ebp,esp
    mov  eax,[ebp+8]        ; EAX = n
    cmp  eax,0              ; n > 0 인가?
    ja   L1                 ; 그러면 재귀 단계로
    mov  eax,1              ; 아니면 (n = 0) 1을 돌려준다
    jmp  L2
L1: dec  eax
    push eax                ; n - 1을 넣고
    call Factorial          ; 자기를 부른다
ReturnFact:                 ; 재귀 호출이 돌아올 때마다 여기부터 실행된다
    mov  ebx,[ebp+8]        ; EBX = 이 호출의 n
    mul  ebx                ; EAX = EAX × EBX
L2: pop  ebp
    ret  4                  ; n 한 칸을 치우고 돌아간다
Factorial ENDP

mul ebx는 EAX에 EBX를 곱해 결과의 아래 32비트를 EAX에, 위 32비트를 EDX에 넣는 명령이다1.

3!을 따라가기

main이 ESP = 00001000h, EBP = 00001010h에서 push 3, call Factorial을 한다. 호출은 네 번 일어난다1.

내려가는 길:

호출 받은 \(n\) = [ebp+8] 그 호출의 EBP 한 일
1 3 00000FF4 \(3 > 0\) → 2를 넣고 자기를 부른다
2 2 00000FE8 \(2 > 0\) → 1을 넣고 자기를 부른다
3 1 00000FDC \(1 > 0\) → 0을 넣고 자기를 부른다
4 0 00000FD0 \(n = 0\) → EAX = 1, 돌아간다

네 번째 호출이 mov ebp,esp를 마친 순간의 스택이다. 이때가 가장 깊다.

   주소        든 값
 00000FFC   00000003   n = 3                    ┐
 00000FF8   ReturnMain (main으로 돌아갈 주소)    │ 호출 1의 프레임
 00000FF4   00001010   main의 EBP               ┘
 00000FF0   00000002   n = 2                    ┐
 00000FEC   ReturnFact                          │ 호출 2
 00000FE8   00000FF4   호출 1의 EBP             ┘
 00000FE4   00000001   n = 1                    ┐
 00000FE0   ReturnFact                          │ 호출 3
 00000FDC   00000FE8   호출 2의 EBP             ┘
 00000FD8   00000000   n = 0                    ┐
 00000FD4   ReturnFact                          │ 호출 4
 00000FD0   00000FDC   호출 3의 EBP             ┘  ← EBP, ESP

프레임 하나는 \(n\), 복귀 주소, 맡아 둔 EBP 세 칸, 12바이트다. 코드는 한 벌이지만 \(n\)은 네 군데(0FFCh, 0FF0h, 0FE4h, 0FD8h)에 따로 있다. 맡아 둔 EBP는 바로 위 프레임의 EBP 자리를 가리켜서, 따라 올라가면 호출 4 → 3 → 2 → 1 → main으로 이어진다.

올라오는 길:

돌아온 곳 pop ebp가 되살린 EBP [ebp+8] mul 뒤 EAX 그 호출의 ret 4 뒤 ESP
(호출 4가 끝남)     1 00000FDC
호출 3의 ReturnFact 00000FDC 1 1 × 1 = 1 00000FE8
호출 2의 ReturnFact 00000FE8 2 1 × 2 = 2 00000FF4
호출 1의 ReturnFact 00000FF4 3 2 × 3 = 6 00001000

main으로 돌아왔을 때 EAX = 6, ESP = 00001000h, EBP = 00001010h다. 5!을 구할 때는 “내려가며 부르기”가 5! = 5 × 4!, 4! = 4 × 3!, …, 0! = 1이고 “되돌아오며 곱하기”가 1, 1 × 1 = 1, 2 × 1 = 2, 3 × 2 = 6, 4 × 6 = 24, 5 × 24 = 120이다.

왜 맞는가

주장. \(n \ge 0\)이고 \(n! < 2^{32}\)이면, \(n\)을 스택에 넣고 Factorial을 불렀을 때 ① EAX = \(n!\)로 돌아오고 ② ESP는 \(n\)을 넣기 전 값이며 ③ EBP는 부르기 전 값이다1.

증명 펼치기

\(n\)에 대한 수학적 귀납법으로 보인다.

  1. 바닥(\(n = 0\)). mov eax,[ebp+8]로 EAX = 0. cmp eax,0 뒤 ja는 뛰지 않는다(0은 0보다 크지 않다). EAX = 1 = \(0!\). — ①
  2. pop ebp가 맡아 둔 EBP를 되살리고 ret 4가 복귀 주소와 \(n\) 한 칸을 꺼낸다. — ②, ③ (스택 프레임의 논증)
  3. 재귀 단계. \(n - 1\)에서 주장이 맞다고 하자(귀납 가정). \(n > 0\)이면 ja가 L1로 뛰고, push eax로 \(n - 1\)을 넣고 자기를 부른다.
  4. 귀납 가정에 따라 돌아왔을 때 EAX = \((n-1)!\), ESP는 push eax 전 값, EBP는 이 호출의 EBP 그대로다. — 가정의 ①, ②, ③
  5. EBP가 그대로이므로 mov ebx,[ebp+8]은 이 호출의 \(n\)을 읽는다. mul ebx로 EAX = \((n-1)! \cdot n = n!\). \(n! < 2^{32}\)이므로 EAX에 다 들어간다. — ①
  6. ESP가 push eax 전 값(= EBP)이므로 pop ebp, ret 4가 2와 같이 ②, ③을 채운다. ∎

끝나는가. 호출마다 \(n\)이 정확히 1 줄고, 0이 되면 더 부르지 않는다. 그래서 호출은 정확히 \(n + 1\)번이다.

스스로 설명해 보기

1. 1번 줄에서 n = 0일 때 ja가 뛰지 않는 이유

cmp eax,0은 0 − 0을 계산해 ZF = 1, CF = 0으로 만든다. ja는 CF = 0이고 ZF = 0일 때만 뛴다. ZF가 1이므로 뛰지 않고 다음 줄 mov eax,1로 간다.

2. 5번 줄에서 [ebp+8]이 n - 1이 아니라 n인 이유

안쪽 호출은 자기 EBP를 새로 세웠지만, 끝에서 pop ebp로 내 EBP를 되살려 놓고 돌아왔다(귀납 가정의 ③). 내 EBP에서 8 위에는 내가 받은 \(n\)이 있다. 안쪽 호출이 받은 \(n - 1\)은 12바이트 아래의 다른 칸에 있었고 이미 치워졌다.

3. 6번 줄에서 ESP가 EBP와 같다는 것은 어디서 나오는가

이 호출이 mov ebp,esp 뒤에 스택에 넣은 것은 push eax 하나뿐이고, 그 한 칸은 안쪽 호출의 ret 4가 치웠다(귀납 가정의 ②). 그래서 ESP는 mov ebp,esp 때의 값, 곧 EBP와 같다.

이 증명의 핵심 아이디어는?

“한 번의 호출이 스택과 EBP를 원래대로 돌려놓는다”를 주장에 함께 넣은 것이다. 답(EAX)만 주장하면 5번 줄에서 [ebp+8]이 여전히 \(n\)이라는 것을 댈 근거가 없다. 프레임을 되돌린다는 약속이 있어야 호출 여러 겹이 서로를 망가뜨리지 않는다.

이 방법을 쓸 수 있는 다른 상황은?

프로시저가 다른 프로시저를 부르는 모든 경우에 같은 약속(들어올 때와 나갈 때 ESP·EBP가 같다)을 쓴다. 재귀로 정의된 구조(트리, 문법)를 따라 내려가는 프로시저의 정확성도 같은 식으로 보인다: 재귀적 정의와 구조적 귀납법.

복잡도

  값
호출 횟수 \(n + 1\)
실행하는 명령 수 \(12n + 9\) (재귀 단계 호출마다 12개, 바닥 호출 9개)
스택 \(12(n + 1)\)바이트

시간과 스택이 모두 \(n\)에 비례한다. 최선·최악의 구분은 없다. 입력 \(n\)이 정해지면 길이 하나로 정해진다. 12!을 구하면 13번 불려 156바이트를 쓴다. 이때 앞쪽 프레임은 위에서부터 (12, ReturnMain, ebp₀), (11, ReturnFact, ebp₁), (10, ReturnFact, ebp₂), (9, ReturnFact, ebp₃) 순서로 쌓이고, 호출마다 12바이트씩 늘어난다. 반복문으로 짜면 스택을 더 쓰지 않는다1.

활용

  • 구현과 검증: 47_recursive-procedure_impl.py. 연습: 재귀 호출 스택 추적 연습
  • 고급 언어의 재귀 함수는 모두 이 모양으로 번역된다. 컴파일러가 호출마다 프레임을 쌓고 걷는 코드를 만든다. 함수 호출의 코드 생성
  • 흔한 실수와 한계1.
    • 바닥 조건을 빼먹는다. CalcSum에서 jz L2를 지우면 ECX가 0을 지나 계속 줄면서 스택이 끝없이 자란다.
    • 음수를 넣는다. ja는 부호 없이 견주므로 −1(FFFFFFFFh)은 아주 큰 수로 보인다. 40억 번 넘게 자기를 부르려다 스택이 바닥난다.
    • 13!부터는 틀린다. 13! = 6,227,020,800은 32비트(약 42억 9천만)를 넘는다. mul이 넘친 부분을 EDX에 넣고 EAX에는 아래 32비트 7328CC00h만 남는다.
    • Factorial은 EBX와 EDX를 맡아 두지 않고 고쳐 쓴다. 부르는 쪽이 이 두 레지스터에 든 값을 계속 쓰려면 미리 맡겨야 한다.
  • 돌아온 뒤 할 일이 없는 재귀(CalcSum)는 값을 레지스터에만 둬도 된다. 돌아온 뒤 할 일이 있는 재귀(Factorial)는 호출마다 값을 프레임에 둬야 한다1.

연결

자주 하는 오해

“자기를 다시 부르면 n이 든 자리가 덮어써져서, 돌아왔을 때 n이 바뀌어 있다”

틀렸다. 코드가 한 벌이고 [ebp+8]이라는 글자도 하나라서 자리도 하나일 것처럼 보인다. 그런데 [ebp+8]은 “지금 EBP에서 8 위”라는 뜻이고, EBP가 호출마다 다르다. 3!을 구할 때 네 호출의 EBP는 0FF4h, 0FE8h, 0FDCh, 0FD0h이고, 그래서 \(n\)이 든 주소도 0FFCh, 0FF0h, 0FE4h, 0FD8h로 다 다르다. 안쪽 호출은 끝날 때 pop ebp로 바깥 호출의 EBP를 되살리므로, 돌아온 바깥 호출이 [ebp+8]을 읽으면 자기 \(n\)이 나온다. 확인하는 법: 올라오는 길의 표에서 [ebp+8]이 1, 2, 3으로 호출마다 제 값을 읽는지 본다. 반대로 값을 레지스터 하나에만 두면 정말로 덮인다. CalcSum의 ECX는 돌아왔을 때 0이다.

확인 문제

C1 재귀 프로시저에 꼭 있어야 하는 두 갈래를 쓰고, Factorial의 프레임 하나에 든 세 가지와 그 크기를 쓰라.

답: 자기를 부르지 않고 답을 내는 바닥 조건과, 문제를 더 작게 만들어 자기를 부르는 재귀 단계. 프레임에는 \(n\), 복귀 주소, 맡아 둔 EBP가 4바이트씩 들어 12바이트다.

C2 ESP = 00001000h에서 push 2, call Factorial을 한다. 호출은 몇 번 일어나는가? 가장 깊을 때의 ESP와, 그때 스택에 든 아홉 칸을 높은 주소부터 쓰라(main의 EBP는 00001010h).

답: 세 번. 가장 깊을 때 ESP = 00000FDCh(36바이트). 높은 주소부터 2, ReturnMain, 00001010h / 1, ReturnFact, 00000FF4h / 0, ReturnFact, 00000FE8h.
이유: 호출마다 12바이트. 맡아 둔 EBP 자리는 0FF4h, 0FE8h, 0FDCh이고 각 칸에는 바로 위 프레임의 EBP가 들어 있다1.

C3 ReturnFact: 아래의 두 줄 mov ebx,[ebp+8]과 mul ebx가 하는 일을 한 문장으로 쓰라.

답: 안쪽 호출이 돌려준 \((n-1)!\)에 이 호출이 받은 \(n\)을 곱해 \(n!\)을 EAX에 만든다.

C4 재귀 호출에서 돌아온 직후 [ebp+8]이 안쪽 호출의 \(n - 1\)이 아니라 이 호출의 \(n\)을 읽는다는 것은 어느 명령 덕분인가?

답: 안쪽 호출 끝의 pop ebp. 안쪽 호출은 들어오면서 내 EBP를 스택에 맡겼고(push ebp), 나가면서 그것을 되살렸다. EBP가 내 프레임을 다시 가리키므로 8 위의 칸은 내가 받은 \(n\)이다.

C5 CalcSum은 push ebp도 [ebp+8]도 없이 재귀를 한다. Factorial은 왜 그렇게 못 하는가?

답: CalcSum은 자기를 부르고 돌아온 뒤 할 일이 ret뿐이라, 돌아왔을 때 ECX나 EAX의 옛 값이 필요 없다. Factorial은 돌아온 뒤에 자기의 \(n\)을 곱해야 한다. 안쪽 호출들이 같은 레지스터를 고쳐 쓰므로 \(n\)을 레지스터에 둘 수 없고, 호출마다 따로 있는 스택 칸에 둬야 한다.
이유: CalcSum이 끝났을 때 ECX는 처음의 5가 아니라 0이다. 레지스터 하나는 모든 호출이 함께 쓴다1.

C6 “Factorial은 어떤 32비트 수를 넣어도 맞는 값을 돌려준다”가 틀렸음을 보이는 입력 둘을 서로 다른 이유로 들라.

답: ① \(n = 13\): 13!이 \(2^{32}\)를 넘어 EAX에는 아래 32비트(7328CC00h = 1,932,053,504)만 남는다. ② \(n = -1\)(FFFFFFFFh): ja가 부호 없이 견주어 “0보다 크다”고 보고 재귀로 들어간다. 바닥에 닿기 전에 스택이 바닥난다.

  1. 시작 주소는 설명용으로 정한 값이다. 실행 결과는 실제 어셈블러가 아니라 파이썬 흉내로 확인했다(검증 줄의 코드). ↩ ↩2 ↩3 ↩4 ↩5 ↩6 ↩7 ↩8 ↩9 ↩10 ↩11