소개
꼬리 호출 재귀
어떤 함수가 마지막으로 실행하는 동작이 자기 자신을 호출하는 것이라면, 그 함수는 꼬리 재귀 함수예요.
함수가 호출될 때마다, 지역 변수와 인자를 담은 _스택 프레임_이 함수 호출 스택 맨 위에 쌓여요.
함수가 반환되면, 그 스택 프레임은 스택에서 제거돼요.
꼬리 재귀 함수는 꼬리 호출 최적화(또는 꼬리 호출 제거)를 가능하게 해요.
이전 함수가 더 이상 그 스택 프레임을 필요로 하지 않는다고 보장될 때, 다음 함수 호출이 마지막 스택 프레임을 재사용할 수 있게 해주는 최적화예요.
이는 함수 호출 스택이 넘치는 문제를 완화해줘요. 함수 호출 스택에 프레임이 너무 많이 쌓여서 새로운 프레임을 만들 메모리가 남아 있지 않은 상황을 말해요.
Elm의 꼬리 호출 최적화
특정 조건에서는 Elm 컴파일러가 JavaScript로 컴파일할 때 꼬리 호출 최적화를 자동으로 수행할 수 있어요.
재귀 함수에서 어떤 분기의 마지막 연산이 함수 자신을 단순한 함수 적용으로 호출하는 것일 때 이 최적화가 일어날 수 있어요.
몇 가지 예시를 살펴볼까요?
factorial : Int -> Int
factorial n =
if n <= 1 then
n
else
n * factorial (n-1)
위 구현은 꼬리 재귀가 아니에요. else 분기의 마지막 연산이 n *라는 곱셈이기 때문이에요.
factorial : Int -> Int
factorial n =
factorialHelper n n
factorialHelper : Int -> Int -> Int
factorialHelper n resultSoFar =
if n <= 1 then
resultSoFar
else
factorialHelper (n-1) (n * resultSoFar)
위 구현은 꼬리 재귀이고 최적화될 거예요. else 분기의 마지막 연산이 factorialHelper가 자기 자신을 호출하는 것이기 때문이에요.
타입 시그니처가 Int -> Int인 함수에서는 이렇게 할 수 없어요. 그래서 실제로는 꼬리 호출 최적화를 위해 헬퍼 함수를 정의하는 경우가 많아요.
지침
파이퍼는 파이 굽기에 푹 빠져 있어요.
자기 이름 때문에 파이 굽기를 시작한 건지, 아니면 취미에 맞춰 이름을 바꾼 건지는 아무도 몰라요.
언뜻 보기에는 후자가 그럴듯해 보이지 않지만, 사실 파이퍼는 파이에 완전히 매료되어 있어요.
그녀는 늘 부엌에서 이것저것 만지작거리며 레시피를 다듬고 솜씨를 키우는데, 친구들은 그런 모습을 무척 좋아해요.
가장 최근에 빠진 건 뭘까요?
가장 좋아하는 숫자의 도움을 받아, 수학적으로 완벽할 정도로 최대한 둥근 파이를 굽는 거예요. 짐작하셨겠지만, 바로 π예요.
파이퍼는 π를 반복적으로 계산하는 멋진 공식을 찾아냈어요. 바로 Newton/Euler Convergence Transformation이에요.
π / 2 = sum for k from 0 to infinity of ( k! ) / ( 2 * k + 1 )!!
π를 계산해서 파이퍼가 수학적으로 완벽한 파이를 굽도록 도와줘요.
1. 팩토리얼
먼저 몸풀기부터 해 봐요.
보통 !로 쓰는 팩토리얼 연산자는 다음과 같이 정의해요.
0! = 1
n! = 1 * 2 * 3 * ... * n
팩토리얼을 꼬리 재귀 방식으로 계산하는 factorial 함수를 정의해요.
factorial 4
-- 24
2. 이중 팩토리얼
보통 !!로 쓰는 이중 팩토리얼 연산자는 다음과 같이 정의해요.
0!! = 1
n!! = 1 * 3 * 5 * ... * n (for odd n)
n!! = 2 * 4 * 6 * ... * n (for even n)
이중 팩토리얼을 꼬리 재귀 방식으로 계산하는 doubleFactorial 함수를 정의해요.
factorial 5
-- 15
factorial 6
-- 48
Newton/Euler Convergence Transformation 공식에서 정해진 개수의 항을 사용해 π를 꼬리 재귀 방식으로 근사하는 pipersPi 함수를 정의해요.
π / 2 = sum for k from 0 to infinity of ( k! ) / ( 2 * k + 1 )!!
첫 번째 항을 함께 계산해 봐요.
상한을 무한대가 아니라 0으로 두면 다음과 같아요.
π / 2 ≈ Sum for k from 0 to 0 of ( k! ) / ( 2 * k + 1 )!!
π / 2 ≈ ( 0! ) / ( 2 * 0 + 1 )!!
π / 2 ≈ 0! / 0!!
π / 2 ≈ 1 / 1
π / 2 ≈ 1
π ≈ 2
항이 하나 늘어날 때마다 근삿값은 더 정확해져요.
pipersPi 0
-- 2.0
pipersPi 1
-- 2.6666666
학습 연습 문제
