꼬리 재귀

3. 구문 형식

꼬리 호출은 함수의 구문적 끝 바로 앞에 위치할 수 있다. 다음은 그 예시이다.

```javascript

function foo(data) {

a(data);

return b(data);

}

```

여기서 `a(data)`와 `b(data)`는 모두 호출이지만, `b`는 프로시저가 반환하기 전에 실행하는 마지막 항목이므로 꼬리 위치에 있다. 그러나 모든 꼬리 호출이 반드시 서브루틴의 구문적 끝에 위치하는 것은 아니다.

```javascript

function bar(data) {

if (a(data)) {

return b(data);

}

return c(data);

}

```

여기서 `b`와 `c`에 대한 호출은 모두 꼬리 위치에 있다. 이는 각 호출이 if-분기의 끝에 위치하기 때문이며, 첫 번째 호출이 `bar` 본문의 구문적 끝에 있지 않더라도 마찬가지이다.

4. 예제 프로그램

Scheme, C, Prolog, 하스켈 등 다양한 프로그래밍 언어에서 꼬리 재귀 및 꼬리 재귀 모듈로 cons 예제를 살펴본다.

'''꼬리 재귀 예제 (Scheme)'''^[7]

Scheme을 사용한 꼬리 재귀 예시는 다음과 같다.

• 일반적인 재귀 함수 (팩토리얼 계산)

• 꼬리 재귀를 활용한 팩토리얼 계산 함수

• C를 이용한 연결 리스트 복제

위 C 코드는 꼬리 재귀가 아니다. 재귀 호출 `duplicate(ls->next)`의 결과를 호출 후 `next` 필드에 연결해야 하기 때문이다.

• 꼬리 재귀 형태로 변환 (C)

`next` 필드를 채우는 책임을 재귀 호출 자체에 넘겨 꼬리 호출이 되도록 한다.

• 반복적 구현으로 변환 (C)

4. 1. 꼬리 재귀 예제 (Scheme)

• `fact-iter (1 4)` 호출
• `fact-iter (4 3)` 호출
• `fact-iter (12 2)` 호출
• `fact-iter (24 1)` 호출
• 24 반환

4. 2. 꼬리 재귀 모듈로 cons

꼬리 재귀 변환에서 이러한 호출은 먼저 새로운 리스트 노드를 생성하고 해당 `first` 필드를 설정한 다음, 노드의 `rest` 필드에 대한 포인터를 인수로 사용하여 꼬리 호출을 수행하여 재귀적으로 채우는 방식으로 변환된다. 게으르게 평가되는 데이터 생성자 아래에서 재귀가 ''보호''될 때 동일한 효과가 달성되는데, 이는 하스켈과 같은 게으른 프로그래밍 언어에서 자동으로 달성된다.

다음은 연결 리스트를 복제하는 C로 작성된 재귀 함수이다.

이 형태에서 함수는 꼬리 재귀가 아닌데, 재귀 호출이 입력 리스트의 나머지를 복제한 후에 제어가 호출자에게 반환되기 때문이다. 재귀 호출 전에 'head' 노드를 할당하더라도, 재귀 호출의 결과를 호출 ''후'' `next` 필드에 연결해야 한다.

그래서 함수는 ''거의'' 꼬리 재귀적이다. Warren의 방법은 `next` 필드를 채우는 책임을 재귀 호출 자체에 밀어넣어 꼬리 호출이 되도록 한다. 센티넬 헤드 노드를 사용하여 코드를 단순화하면 다음과 같다.

이제 호출된 함수는 반환된 리스트의 시작 부분에 호출자가 추가하는 대신, 성장하는 리스트의 끝에 추가한다. 작업은 재귀 호출이 더 진행되기 ''전''에 리스트의 시작 부분에서 ''앞으로'' 진행되는 방식(그리고 그 결과가 반환된 후)이 아니라 재귀 호출이 결과를 반환한 ''후''에 리스트의 끝 부분에서 ''뒤로'' 진행되는 방식이다. 따라서 이는 재귀 계산을 반복적인 계산으로 바꾸는 누적 매개변수 기법과 유사하다.

이 기술의 특징은, 꼬리 호출 최적화가 있는 경우, 상위 프레임이 실행 호출 스택에 생성되어 꼬리 재귀 호출 함수가 자체 호출 프레임으로 재사용할 수 있다는 것이다.

꼬리 재귀 구현은 이제 명시적으로 반복적인 구현, 즉 누적 루프로 변환될 수 있다.

5. 역사

1977년 시애틀에서 열린 ACM 컨퍼런스에서 발표된 논문에서 가이 L. 스틸은 프로시저 호출의 꼬리 위치에 있는 프로시저 호출을 직접적인 제어 이전으로 취급하여 불필요한 스택 조작 연산을 제거할 수 있다고 언급했다.^[10] 이러한 "꼬리 호출"은 Lisp에서 매우 일반적이었기 때문에, 이러한 최적화는 프로시저 호출 비용을 상당히 줄여주었다. 스틸은 프로시저 호출의 부실한 구현이 GOTO가 프로시저 호출에 비해 저렴하다는 인식을 만들었다고 주장했다. 또한 "일반적으로 프로시저 호출은 매개변수를 전달하는 GOTO 문으로 생각할 수 있으며, [기계어] JUMP 명령어로 일관되게 코딩할 수 있다"고 주장하면서, 기계어 스택 조작 명령은 "최적화로 간주되어야 한다(그 반대가 아니라!)"고 말했다.^[10] 스틸은 Lisp에서 잘 최적화된 수치 알고리즘이 당시 상업용 포트란 컴파일러에서 생성된 코드보다 더 빠르게 실행될 수 있음을 제시했는데, 이는 Lisp에서 프로시저 호출 비용이 훨씬 낮았기 때문이다.^[10] 제럴드 제이 서스먼과 함께 개발한 Lisp 방언인 Scheme은 모든 인터프리터에서 꼬리 호출 제거를 구현하도록 보장한다.^[11]

6. 구현 방법

꼬리 재귀는 함수형 프로그래밍, 논리 프로그래밍, Lisp 프로그래밍 언어 계열에서 반복을 구현하는 중요한 방법이다. 이러한 언어에서 꼬리 재귀는 반복을 구현하는 가장 일반적인 방법(때로는 유일한 방법)이다. Scheme 언어 명세는 꼬리 호출이 스택을 증가시키지 않도록 최적화되어야 한다고 요구한다.^[12] Perl에서는 함수 이름을 사용하는 "goto"문의 변형을 통해 꼬리 호출을 명시적으로 만들 수 있다(goto &NAME;).^[12]

하지만 함수 인자와 지역 변수를 호출 스택에 저장하는 언어 구현의 경우, 일반화된 꼬리 호출 최적화(상호 꼬리 재귀 포함)를 구현하기 어렵다. 호출된 함수의 활성 레코드 크기가 호출한 함수의 활성 레코드 크기와 다르면 스택 프레임을 추가로 정리하거나 크기를 조정해야 할 수 있기 때문이다. 따라서 꼬리 재귀 최적화는 비교적 간단하지만, 일반적인 꼬리 호출 최적화는 효율적으로 구현하기 어려울 수 있다.

예를 들어, 자바 가상 머신(JVM)에서는 꼬리 재귀 호출은 기존 호출 스택을 재사용하므로 제거할 수 있지만, 일반 꼬리 호출은 호출 스택을 변경해야 하므로 제거할 수 없다.^[13][14] 결과적으로 JVM을 대상으로 하는 Scala와 같은 함수형 언어는 직접 꼬리 재귀는 효율적으로 구현할 수 있지만, 상호 꼬리 재귀는 구현할 수 없다.

GNU 컴파일러 모음(GCC), LLVM/Clang, 인텔 C 컴파일러(Intel) 컴파일러는 더 높은 최적화 수준에서 또는 -foptimize-sibling-calls 옵션을 사용하면 C (프로그래밍 언어) 및 다른 언어에 대해 꼬리 호출 최적화를 수행한다.^[15][16][17] 컴파일러는 주어진 언어 구문이 명시적으로 지원하지 않더라도, 호출자와 호출된 함수의 반환 유형이 동일하고, 두 함수에 전달된 인자 유형이 같거나 호출 스택에서 동일한 양의 총 저장 공간을 요구하는 경우 이 최적화를 수행할 수 있다.^[18]

다양한 구현 방법이 존재한다. 함수형 언어에서는 자신의 반환값에 다른 함수의 반환값을 사용하는 꼬리 호출을 통한 프로그래밍이 자연스럽다. 특히 Scheme은 최적화를 수행해야 하는 패턴을 형식적으로 규정하고, 최적화를 수행하도록 사양으로 정하고 있다.

함수형 언어 처리계에는 프로그램 전체를 지속 전달 스타일로 변환하여 모든 호출을 꼬리 호출로 변환하는 기법도 있다.

대체 모델 관점에서 보면, 어떤 절차가 반환하는 값은 그 안에서 마지막으로 호출한 절차의 결과와 같고, 그 외의 부분은 과정의 분기 또는 부작용을 가질 경우에만 의미를 가진다. 따라서 함수적인 관점에서는 절차의 꼬리 부분만 고려하면 되며, 여기서 재귀가 일어나는 경우를 꼬리 재귀라고 한다.

Common Lisp에서의 꼬리 재귀 예:

```lisp

(defun fact (n)

(labels ((ifact (n r)

(if (= n 0)

r

(ifact (- n 1) (* n r)))))

(ifact n 1)))

```

F#에서의 꼬리 재귀 예:

```lisp

// 비 꼬리 재귀

let rec fact n =

if n = 0 then 1 else fact (n - 1) * n

// 꼬리 재귀

let fact n =

let rec ifact n r =

if n = 0 then r else ifact (n - 1) (n * r)

ifact n 1

6. 1. 어셈블리에서 구현

6. 2. 트램펄린을 통한 구현

6. 3. 가비지 수집을 이용한 구현 (Chicken Scheme)

7. while 문과의 관계

꼬리 재귀는 명시적 반복문인 `while` 구문으로 변환될 수 있다. 예를 들어,

```

'''절차''' foo(''x'')

'''만약''' ''p''(''x'')

'''반환''' bar(''x'')

'''그렇지 않으면'''

'''반환''' foo(baz(''x''))

```

는

```

'''절차''' foo(''x'')

'''while''' '''참'''

'''만약''' ''p''(''x'')

'''반환''' bar(''x'')

'''그렇지 않으면'''

''x'' ← baz(''x'')

```

로 변환할 수 있다. 여기서 ''x''는 여러 변수를 포함하는 튜플일 수 있다. 이 경우 종속성을 고려하여 할당문 ''x'' ← baz(''x'')를 구현하는 데 주의해야 한다. 보조 변수를 도입하거나 ''스왑'' 구문을 사용할 수 있다.

더 일반적으로,

```

'''절차''' foo(''x'')

'''만약''' ''p''(''x'')

'''반환''' bar(''x'')

'''그렇지 않고 만약''' ''q''(''x'')

'''반환''' baz(''x'')

...

'''그렇지 않고 만약''' ''r''(''x'')

'''반환''' foo(qux(''x''))

...

'''그렇지 않으면'''

'''반환''' foo(quux(''x''))

```

는 다음과 같이 변환될 수 있다.

```

'''절차''' foo(''x'')

'''while''' '''참'''

'''만약''' ''p''(''x'')

'''반환''' bar(''x'')

'''그렇지 않고 만약''' ''q''(''x'')

'''반환''' baz(''x'')

...

'''그렇지 않고 만약''' ''r''(''x'')

''x'' ← qux(''x'')

...

'''그렇지 않으면'''

''x'' ← quux(''x'')

```

예를 들어, 다음 줄리아 프로그램은 팩토리얼의 비 꼬리 재귀적 정의 `fact`를 제공한다.



function factorial(n)

if n == 0

return 1

else

return n * factorial(n - 1)

end

end



실제로, `n * factorial(n - 1)`는 `factorial`에 대한 호출을 래핑한다. 그러나 '누산기'라고 하는 인수 `a`를 추가하여 꼬리 재귀적 정의로 변환할 수 있다.<sup>[7]</sup>

다음은 팩토리얼의 꼬리 재귀적 정의 `fact_iter`를 제공하는 줄리아 프로그램이다.



function factorial(n::Integer, a::Integer)

if n == 0:

return a

else

return factorial(n - 1, n * a)

end

end

function factorial(n::Integer)

return factorial(n, 1)

end



다음은 팩토리얼의 반복적 정의 `fact_iter`를 제공하는 줄리아 프로그램이다.



function fact_iter(n::Integer, a::Integer)

while n > 0

a = n * a

n = n - 1

end

return a

end

function factorial(n::Integer)

return fact_iter(n, one(n))

end



일반적으로 재귀 호출이 가능한 언어에서는 서브루틴 호출 시마다 스택에 호출처로 되돌아오기 위한 정보를 저장한다. 따라서 재귀가 너무 깊어지면 스택 오버플로우로 프로그램이 비정상 종료될 수 있다.

이러한 경우, 다음과 같이 루프로 변환하여 이를 피할 수 있다.

```ada

{ 변환 전 }

function F (a1:T1, a2:T2, ..., an:Tn) : T0

begin

P ;

return func (b1, b2, ..., bn) ;

end ;

{ 변환 후 }

function F (a1:T1, a2:T2, ..., an:Tn) : T0

begin

loop

P ;

a1 := b1 ;

a2 := b2 ;

:

an := bn ;

end loop ;

end ;

{

Ti는 자료형, P는 프로시저, bi는 값 또는 a1~an에 대한 부작용이 없는 식이다.

그 외의 식별자는 변수를 나타내며 P 안에 최소 1개의 return 문이 없으면

스택 오버플로우 또는 무한 루프가 발생한다.

}

8. 언어 지원

참조

<sub>[1]</sub> 서적 Advanced Compiler Design Implementation https://archive.org/[...] Morgan Kaufmann 1997-08-15
<sub>[2]</sub> 웹사이트 The LLVM Target-Independent Code Generator — LLVM 7 documentation http://llvm.org/docs[...]
<sub>[3]</sub> 웹사이트 recursion - Stack memory usage for tail calls - Theoretical Computer Science https://cstheory.sta[...] Cstheory.stackexchange.com 2013-03-21
<sub>[4]</sub> 웹사이트 Revised^6 Report on the Algorithmic Language Scheme http://www.r6rs.org/[...] R6rs.org 2013-03-21
<sub>[5]</sub> 웹사이트 Revised^6 Report on the Algorithmic Language Scheme - Rationale http://www.r6rs.org/[...] R6rs.org 2013-03-21
<sub>[6]</sub> 웹사이트 Revised^6 Report on the Algorithmic Language Scheme http://www.r6rs.org/[...] R6rs.org 2013-03-21
<sub>[7]</sub> 서적 Structure and Interpretation of Computer Programs https://archive.org/[...] MIT Press 1984
<sub>[8]</sub> 간행물 DAI Research Report 141 University of Edinburgh 1980
<sub>[9]</sub> 간행물 Technical Report TR19: Unwinding Structured Recursions into Iterations http://www.cs.indian[...] Indiana University 1974-12
<sub>[10]</sub> 서적 Proceedings of the 1977 annual conference on - ACM '77
<sub>[11]</sub> 학술지 Revised<sup>5</sup> Report on the Algorithmic Language Scheme http://www.schemers.[...] 1998-08
<sub>[12]</sub> 웹사이트 goto http://perldoc.perl.[...] perldoc.perl.org 2013-03-21
<sub>[13]</sub> 뉴스 What is difference between tail calls and tail recursion? https://stackoverflo[...] Stack Overflow
<sub>[14]</sub> 뉴스 What limitations does the JVM impose on tail-call optimization http://programmers.s[...] Programmers Stack Exchange
<sub>[15]</sub> 웹사이트 LLVM Language Reference Manual, section: The LLVM Target-Independent Code Generator, sub: Tail Call Optimization http://llvm.org/docs[...] The LLVM Project 2018-06-24
<sub>[16]</sub> 웹사이트 Using the GNU Compiler Collection (GCC): Optimize Options https://gcc.gnu.org/[...]
<sub>[17]</sub> 웹사이트 foptimize-sibling-calls https://software.int[...]
<sub>[18]</sub> 웹사이트 Tackling C++ Tail Calls http://www.drdobbs.c[...]
<sub>[19]</sub> 웹사이트 proper tail recursion for gcc https://gcc.gnu.org/[...] GCC Project 2015-03-10
<sub>[20]</sub> 뉴스 Bouncing on your tail http://blog.function[...] Functional Fun 2008-04-09
<sub>[21]</sub> 문서 "CONS Should Not CONS Its Arguments, Part II: Cheney on the M.T.A." http://home.pipeline[...]
<sub>[22]</sub> 웹사이트 (recur expr*) https://clojure.org/[...]
<sub>[23]</sub> 웹사이트 Recursion http://elixir-lang.o[...]
<sub>[24]</sub> 웹사이트 Functional Programming in Elm: Tail-Call Elimination https://functional-p[...]
<sub>[25]</sub> 웹사이트 Tail Calls in F# https://blogs.msdn.m[...] Microsoft 2011-07-08
<sub>[26]</sub> 웹사이트 proposal: Go 2: add become statement to support tail calls https://github.com/g[...]
<sub>[27]</sub> 웹사이트 Tail recursion - HaskellWiki https://wiki.haskell[...] 2019-06-08
<sub>[28]</sub> 웹사이트 Worth watching: Douglas Crockford speaking about the new good parts of JavaScript in 2014 http://bdadam.com/bl[...]
<sub>[29]</sub> 웹사이트 ECMAScript 6 in WebKit https://www.webkit.o[...] 2015-10-13
<sub>[30]</sub> 웹사이트 Functions: infix, vararg, tailrec - Kotlin Programming Language https://kotlinlang.o[...]
<sub>[31]</sub> 웹사이트 Lua 5.3 Reference Manual https://www.lua.org/[...]
<sub>[32]</sub> 웹사이트 goto - perldoc.perl.org http://perldoc.perl.[...]
<sub>[33]</sub> 웹사이트 baruchel/tco https://github.com/b[...] 2022-03-29
<sub>[34]</sub> 웹사이트 Neopythonic: Tail Recursion Elimination http://neopythonic.b[...] 2009-04-22
<sub>[35]</sub> 웹사이트 What's new in R 4.4.0? https://www.jumpingr[...] 2024-04-28
<sub>[36]</sub> 웹사이트 The Racket Reference https://docs.racket-[...]
<sub>[37]</sub> 웹사이트 Ruby Tail Call Optimisation https://ruby-doc.org[...]
<sub>[38]</sub> 웹사이트 Rust FAQ https://prev.rust-la[...]
<sub>[39]</sub> 웹사이트 Scala Standard Library 2.13.0 - scala.annotation.tailrec https://www.scala-la[...] 2019-06-20
<sub>[40]</sub> 웹사이트 Revised^5 Report on the Algorithmic Language Scheme http://www.schemers.[...]
<sub>[41]</sub> 웹사이트 Revised^6 Report on the Algorithmic Language Scheme http://www.r6rs.org/[...]
<sub>[42]</sub> 웹사이트 Does Swift implement tail call optimization? https://stackoverflo[...] 2024-03-13
<sub>[43]</sub> 웹사이트 tailcall manual page - Tcl Built-In Commands http://www.tcl.tk/ma[...]
<sub>[44]</sub> 웹사이트 Documentation - the Zig Programming Language https://ziglang.org/[...]
<sub>[45]</sub> 서적 bit 単語帳 共立出版 1990-08-15
<sub>[46]</sub> 웹인용 Annotations {{!}} Scala Documentation https://docs.scala-l[...] 2018-03-04