재귀
함수는 자기 자신을 호출하면 재귀 함수예요.
함수 호출과 루프의 중요한 차이 한 가지는, 함수를 호출하면 반환할 주소를 스택에 넣는다는 점이에요.
그래서 재귀 함수는 대개 이에 상응하는 루프보다 스택 공간을 더 많이 차지해요.
그 결과, 자기 자신을 계속 호출하는 함수는 결국 스택 공간을 모두 고갈시킬 수 있어요.
이것을 스택 오버플로라고 해요.
그래서 모든 재귀 함수에는 적어도 하나의 기저 사례가 있어야 해요.
기저 사례란 함수가 자기 자신을 호출하지 않고 반환하는 상황을 말해요.
재귀 호출은 결국 기저 사례에 도달해야 해요.
예를 들어, 팩토리얼 함수 n! = n * (n - 1) * ... * 1은 1을 기저 사례로 두고 재귀적으로 정의할 수 있어요:
factorial:
; the argument `n` is passed on `rdi`
; the factorial will be returned on `rax`
cmp rdi, 1
jle .base_case ; base case -> if rdi <= 1, return 1
push rdi ; save n
dec rdi ; rdi = n - 1
call factorial ; recursive call, rax = (n - 1)!
pop rdi ; restore n
imul rax, rdi ; rax = n * (n - 1)! = n!
ret
.base_case:
mov rax, 1
ret
factorial은 재귀 호출 전에 push rdi를 하고, 호출 뒤에는 pop rdi를 해야 한다는 점에 주목해요.
재귀 호출이 반환된 뒤에 n * (n-1)!을 계산하려면 여전히 n이 필요하기 때문이에요.
피호출자 보존 레지스터를 사용해도 이 문제는 해결되지 않아요.
재귀 함수는 자기 자신을 호출할 수도 있는 호출자이지만, 동시에 다른 어떤 함수의 피호출자이기도 해요.
즉, 이 함수도 피호출자 보존 레지스터를 사용하기 전에 보존하고, 사용한 뒤에는 값을 복원해야 해요.
이는 이전 개념에서 본 것처럼 보통 push/pop 순서로 해요.
재귀 함수의 각 프레임은 기저 사례를 제외하면 자신의 지역 변수를 보존해야 하는 호출자이기도 하므로, 이 push/pop 순서는 프레임마다 반복되어야 해요.
레지스터를 쓰지 않고 변수를 스택에 바로 저장해도 프레임마다 똑같이 8바이트가 들어요.
즉, 각 재귀 호출은 call이 넣는 반환 주소를 위해 스택에 8바이트를 더하고, 저장해야 하는 지역 변수마다 8바이트를 더해요.
함수는 기저 사례에 도달할 때까지 프레임마다 이 바이트를 스택에 계속 더해요.
그제야 역순으로 풀리기 시작하는데, 각 재귀 호출은 필요한 만큼 pop을 하고 마지막에 ret을 해요.
예를 들어 factorial이 인자 10으로 호출되면, 기저 사례인 1에 도달하기 전까지 자기 자신을 아홉 번 호출해요.
그 시점에는 이전 프레임마다 n(8바이트)과 반환 주소(8바이트)를 저장하는 데 144바이트가 사용된 상태예요.
꼬리 호출
어떤 상황에서는 함수가 다른 함수를 호출한 뒤 반환하기 전까지 더 이상 아무 작업도 하지 않아요.
예를 들어 다음을 봐요:
times_three:
imul rax, rdi, 3
ret
triple_of_square:
imul rdi, rdi
call times_three
ret
triple_of_square 함수는:
- 전달받은 인자(
rdi에 있는)를 자기 자신과 곱해서 제곱을 구하고,
- 그다음
times_three를 호출하는데, 이 함수는 전달받은 인자에 3을 곱한 값을 반환해요.
결과적으로 triple_of_square는 3*x²를 반환해요.
여기서 x는 rdi로 전달된 인자예요.
triple_of_square는 times_three를 호출한 뒤 아무 작업도 하지 않고 그냥 반환한다는 점에 주목해요.
이런 상황에서는 call 대신 jmp를 사용해 실행을 호출된 함수로 넘길 수 있어요:
times_three:
imul rax, rdi, 3
ret
triple_of_square:
imul rdi, rdi
jmp times_three
이것을 꼬리 호출이라고 해요.
꼬리 호출의 가장 큰 장점은 call의 추가 비용을 피할 수 있다는 점이에요.
call은 반환 주소를 스택에 넣고, 제어가 그 지점으로 되돌아오려면 짝을 이루는 ret이 있어야 해요.
꼬리 호출은 둘 다 건너뛰어요. 넣을 반환 주소도 없고, 짝을 이룰 추가 ret도 없이 호출된 함수 자신의 ret만 있을 뿐이에요.
꼬리 재귀
꼬리 호출은 반환하기 전에 자기 자신을 여러 번 호출할 수 있는 재귀 함수에 특히 유용해요.
하지만 모든 재귀 호출을 곧바로 꼬리 호출로 바꿀 수 있는 것은 아니에요.
jmp는 제어를 호출된 함수로 넘기므로, 호출자는 꼬리 호출 이후에 더 이상 아무 작업도 할 수 없어요.
예를 들어 앞서 본 factorial 함수는 꼬리 재귀가 아니에요.
재귀 호출 뒤에도 imul rax, rdi를 사용해 결과에 현재 n을 곱해야 하거든요.
이런 상황에서는 중간 계산을 모아 두었다가 마지막에 반환할 누산기를 사용할 수 있을 때가 있어요.
예를 들어 대부분의 작업을 처리하는 factorial_helper를 정의하고, factorial이 누산기를 준비한 뒤 제어를 factorial_helper로 넘길 수 있어요:
factorial_helper:
; the argument `n` is passed on `rdi`
; `rax` is used as an accumulator and will be returned at the end
cmp rdi, 1
jle .base_case
imul rax, rdi ; we accumulate the partial result on `rax`
dec rdi ; rdi = n - 1
jmp factorial_helper ; tail call to accumulate (n - 1)!
.base_case:
ret ; returns the factorial already accumulated on `rax`
factorial:
mov rax, 1 ; initial value for the accumulator
jmp factorial_helper ; tail call
재귀 호출 뒤에 더 이상 하는 일이 없으므로 rdi를 저장할 필요도 없어요.
call도 push rdi도 없으니 각 재귀 반복은 스택에 0바이트를 더해요. 즉 추가 스택 공간을 쓰지 않아요.
이 버전은 스택을 넘치게 하지 않고 아무리 큰 n도 처리할 수 있어요.
더 효율적이면서 더 안전해요.
어떤 경우에는 함수의 순서를 조정하면 헬퍼로 가는 jmp조차 피할 수 있어요.
예를 들어 factorial과 triple_of_square를 이렇게 다시 쓸 수 있어요:
factorial:
mov rax, 1
factorial_helper:
cmp rdi, 1
jle .base_case
imul rax, rdi
dec rdi
jmp factorial_helper
.base_case:
ret
triple_of_square:
imul rdi, rdi
times_three:
imul rax, rdi, 3
ret
위 코드 조각에서는 factorial의 실행이 factorial_helper로 그대로 이어져요.
triple_of_square와 times_three도 마찬가지예요.
두 경우 모두 실행이 순차적으로 이어지는데, 꼬리 함수가 마치 "main" 함수 안의 지역 레이블처럼 보여요.
실제로는 지역 레이블과 함수 사이에 근본적인 차이가 없어요.
x86-64 어셈블리는 어느 쪽에도 특별한 대우를 하지 않아요. 그저 section .text 같은 실행 코드가 담긴 섹션 안의 주소일 뿐이에요.
이런 방식으로 보면, 꼬리 재귀 함수는 재귀 호출이 맨 위로 되돌아가고 기저 사례가 루프를 끝내는 조건인 루프와 본질적으로 같다고 볼 수 있어요.
학습 연습 문제
