재귀와 꼬리재귀(1)

리스트, 트리, 그래프 등등의 모든 데이터 구조는 리커시브 하게 정의되며, 그래프도 정의에 리스트가 사용된다. 이렇게 정의된 객체를 효율적으로 다루기 위해선 어떤 알고리즘이 효율적일까?

이렇게 볼 때, 리커시브 하게 정의되지 않은 객체가 얼마나 될까? 실제 문제를 해결할 때 문제를 정의할 객체는 거의 리커시브 하게 정의되는 것이 대부분이 아닐까?

재귀 호출이 알맞는 경우

알고리즘 자체가 재귀적인 표현이 자연스러운 경우

실제로 모든 자연상의 대상체들도 거의 리커시브 하게 되어있다는 것을 부인할 수는 없는 것 같다. 스도쿠를 풀 때도 리커전이 사용되는 건 게임 서치트리가 말 그대로 트리이기 때문이며, sicp 에서 리커전이 기본 사고방식인 건 객체의 기본적 데이터 구조가 리스트이기 때문이다.

재귀 호출은 변수 사용을 줄여줄 수 있다.

좀 추상적으로 말하자면 mutable state가 취할 수 있는 가능한 경우의 수를 줄여준다. 결과적으로 프로그램에 오류가 생길 (즉, 잘못된 state로 전이할) 가능성이 줄어들고, 프로그램이 맞다는 것을 확인(특수한 경우에는 증명)하기가 쉬워진다.

함수형 언어의 특징이 사이드 이펙트가 없다는 것

물론 단순한 경우에는 오히려 재귀 호출이 직관적으로 이해하기 더 어려울 수도 있다. 하지만 프로그램이 복잡해지면 mutable state를 가능한 한 피하는 것이 오류 없는 프로그램을 짜는 데에 중요한 원칙이 될 수밖에 없다.

mutable state를 가능한 한 피하는 것은 변수의 수를 줄이는 것과 변수가 가질 수 있는 값의 종류 또는 범위를 정확히 제한하는 것이라고 생각하면 된다. 변수의 수를 줄이는 것은 재귀 호출이 도와주고, 변수가 가질 수 있는 값의 종류 또는 범위를 정확히 제한하는 것은 type system이 도와준다.

var sum = 0
for(int i in 0 ... 100 {
  sum += i
}
print(sum)

func sum(_ x: Int, _ acc: Int) -> Int {
  if x > 100 {
    return acc
  }
  return sum(x + 1, x + acc)
}

print(sum(0, 0))

둘 다 0부터 100까지의 합을 구하는 프로그램. 그런데 프로그램 1에는 변수가 두 개 있고, 프로그램2에는 변수가 하나도 없다.

프로그램2에서 x와 acc는 immutable이다.

컴파일러가 꼬리재귀 최적화(tail recursion)를 지원한다면
루프를 사용하는 경우와 동일한 성능을 보장할 수 있다.
stack overflow도 없다.

이런 패턴은 흔히 쓰이는 일반적인 패턴(accumulator pattern)이기 때문에 약간만 익숙해지면 자연스럽게 읽힌다.

재귀의 단점

재귀함수의 단점은 콜스택이 증가한다.
추가적인 메모리 공간이 필요하고 성능이 반복문에 비해 느리다.

컴파일러가 꼬리 재귀 최적화(tail recursion)를 지원하는 경우, 이러한 단점이 해결되어 루프를 사용하는 경우와 동일한 성능을 보장할 수 있다.

함수형 언어의 인기 증가와과 컴파일러가 재귀적인 호출을 최적화 것과 관련성이 있는가?

함수형 언어들은 대부분 처음 세상에 나올 때부터 재귀호출에 대한 최적화를 가지고 나왔다. 처음 나올 때부터 적어도 재귀호출에 관한 똑똑했다.

underlying platform의 특성상 그렇지 않은 경우도 있기는 하다. 예를 들어 jvm에서 돌아가는 함수형 언어들 중에는 mutual tail call optimization을 하지 못하는 언어도 있다.

흔히 쓰이는 컴파일러들이 어떤 재귀호출을 반복문처럼 최적화를 해 내는지?

가장 중요하고 기본적인 최적화는 tail call optimization(TCO)이다. 재귀 함수의 가장 마지막 동작이 자기 자신을 호출하는 경우를 말한다. 이런 경우에는 현재의 stack frame을 굳이 유지할 필요가 없기 때문에 그냥 그 stack frame을 재사용하면 된다. 자기를 다시 부를 때마다 stack frame을 새로 쌓을 필요가 없는 것. 결과적으로 loop와 마찬가지고 동작하게 된다. 하지만 tail call이 아닌 경우, 즉 자기를 다시 호출한 이후 다른 일을 더 해야 한다면 stack frame을 유지하면서 자기 자신에 대한 호출이 리턴까지 기다려야 한다. stack frame을 재사용할 수 없다. 예를 들어 위의 0부터 100까지 더하는 프로그램을 다음과 같이 재귀로 짤 수 있다.

func sum(_ x: Int) -> Int {
  if x == 100 {
    return x
  }
  return x + sum(x + 1)
}

이 경우에는 마지막 라인에서 sum(x + 1)가 리턴한 다음에 x 에 더해야 하기 때문에 x의 값을 계속 유지해야 한다. 고로 stack frame을 재사용할 수 없고 계속 쌓아가야만 한다.
이를 피하기 위해서 함수에 인자를 하나 더 추가해서 (보통 accumulator라고 부른다.) tail call로 만든 것이 저~기 위에 예로 든 구현이다.
언어에 따라서는 겉보기에는 tail call이지만 실재로는 아닌 경우가 있으니 주의해야 한다.
코드 상 가장 마지막 표현이 자기 자신에 대한 호출이지만, local object의 destructor 때문에 실재로는 그렇지 않은 경우가 있어 주의해야 한다.

사실 함수가 마지막으로 하는 일이 자기 자신이 아니라 다른 함수에 대한 호출이어도 tail call이다.
예를 들어 두 함수가 마지막에 서로를 호출하는 mutual recursion도 TCO를 할 수 있다.

언어에 따라서 이런 종류의 최적화를 제공하는 정도가 다르다.
단순히 그런 최적화에 신경을 쓰지 않아서일 수도 있고, 언어 자체의 특성상 안되는 경우도 있고, 그 언어가 돌아가는 플랫폼의 특성상 안 되거나 어려운 경우도 있다. self recursion만 최적화 하고, mutual recursion은 못해주는 경우도 있다.
TCO를 해달라는 keyword나 컴파일러 지시자가 있는 언어도 있어 다양하다.
주로 쓰이는 C/C++ 컴파일러의 경우에는 상당히 잘 해준다.
gcc, msvc++, clang 모두 잘 해준다.

서비스에서 재귀를 써도 좋을까?

stackoverflow 날 정도면 안 쓰는 게 맞으나 depth가 깊지 않은 게 명확하고 이로 인해 immutable 이득도 얻을 수 있으면 쓸 수 있다고 생각한다. 물론 꼬리재귀를 사용하면 stackoverflow에 대한 오류도 방지할 수 있다.

LLVM 은 꼬리재귀(tail call optimization)를 지원한다. 꼬리재귀는 돌아갈 콜 스택이 증가하지 않는다. 다음 이동할 스택 프레임이 자기 자신이기 때문에 추가 메모리 공간을 사용하지 않고 가능하다.

출처

KLDP