정상적인 재귀 및 꼬리 재귀 예제간에 반올림 차이가있는 이유는 무엇입니까?

Question

꼬리 재귀 예를 놀겠다는 거 동안 나는 정상적인 재귀 호출의 결과와 꼬리 재귀 호출 사이의 작은 차이가 발견 :

scala> def fact(n: Int): Double = if(n < 1) 1 else n * fact(n - 1) 
fact: (n: Int)Double 

scala> fact(30) 
res31: Double = 2.6525285981219103E32 

scala> @tailrec def fact(n: Int, acc: Double = 1): Double = if(n < 1) acc else fact(n - 1, n * acc) 
fact: (n: Int, acc: Double)Double 

scala> fact(30) 
res32: Double = 2.652528598121911E32 

그냥 호기심, 누군가가 나에게 설명해 할 수 있습니다 이유 또는 어디 반올림이 발생합니다. 내 생각 엔 스칼라 컴파일러는 꼬리 재귀 버전을 루프로 변환하기 때문에 루프의 반복마다 acc 매개 변수가 할당되고 작은 반올림 오류가 발생합니다.

Answer 1

두 버전이 곱셈을 다른 순서로 수행하므로 다른 반올림이 발생하므로 결과가 달라집니다.

먼저 점의 값을 계산하기 때문에 일반적인 재귀 호출이 발현 n*([n-1]*([n-2]*(...))) 리드 (N-1)가 우선 n으로 곱해 때문에 꼬리 재귀 하나 ((n*[n-1])*[n-2])*... 리드 반면 다음, N에 곱 n-1로 반복합니다.

다른 버전을 반복하여 이론적으로 동일한 대답을 얻도록 버전 중 하나를 다시 작성하십시오.

Answer 2

두 기능이 동일한 순서로 작업을 수행하지 않습니다.

int main(int c, char **v) 
{ 
    printf ("%.16e %.16e\n", 
     30.*29*28*27*26*25*24*23*22*21*20*19*18*17*16*15*14*13*12*11*10*9*8*7*6*5*4*3*2, 
     2.*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20*21*22*23*24*25*26*27*28*29*30); 
} 

인쇄 : C에서

함수의

한 버전 30.*29*...을 계산 (나는 C에서 부동 소수점 예상 작동하는 플랫폼을 사용)

2.6525285981219110e+32 2.6525285981219103e+32 

및 다른 계산은 2.*3*...입니다. 이 두 결과는 약간 다릅니다. 부동 소수점 연산은 연관 적입니다. 그러나 결과에 대해 아무 것도 알아볼 수없는 점에 유의하십시오. 귀하의 함수 중 하나는 정확히 IEEE 754 배정 밀도 표현 30.*29*...을 계산하고 다른 하나는 정확히 2.*3*...을 계산합니다. 둘 다 설계된대로 작동합니다.

내가 추측해야만한다면 2.*3*...이 더 정확할 것으로 예상되지만 (실제 숫자로 얻은 결과에 더 가깝습니다) 두 개의 숫자는 매우 가깝고 실제 결과에 매우 가깝습니다.

Answer 3

스칼라가 꼬리 재귀를 루프로 변환한다는 사실과 다른 점은 차이가 있습니다. 결과는 최적화없이 동일합니다. 루프가하는 것보다 반올림 오류에 관해서도 재귀가 다르게 작용하지는 않습니다.

차이점은 숫자에 곱한 순서입니다. 첫 번째 솔루션은 숫자를 곱하기 전에 1로 끝까지 순환합니다. 따라서 계산은 n * ((n - 1) * (... * (2 * 1)))이 될 것입니다. 꼬리 재귀 버전은 즉시 곱하기 시작하므로 n * (n-1) * ... * 2 * 1을 계산합니다.

물론 일반적으로 곱셈은 연관성이 있기 때문에 두 개가 동일하다고 말할 수 있지만 부동 소수점 산술에는 적합하지 않습니다. 부동 소수점 사용 (x * y) * z은 반올림 오류가 다르게 전파되므로 x * (y * z)과 매우 다를 수 있습니다. 그래서 당신의 행동을 설명합니다.

계승을 구현하기 위해 1에서 n까지의 for 루프와 n에서 1까지 계산되는 for 루프를 사용할 때 동일한 차이점을 볼 수 있습니다.