Factorial은 어떻게 계산됩니까?

Question

Factorial (N)을 계산할 수있는 기능이 있다고 말합니다.

요인 (7)이 각 N에 대한 7 기능 개체를 1에서 7까지 생성합니까?

그리고 필요할 때 그 값을 사용하십시오 (Factorial (8)과 같이 Factorial (7)*8)

Answer 1

언어와 언어 구현에 따라 다릅니다.

많은 기능적 언어 (예 : Haskell)에서 함수는 아무것도 변경하지 않습니다. 값을 반환하기 위해서만. 부작용 부족은 언어가 기능 호출의 결과를 기억/캐시 또는 "메모 화"할 수있게합니다.

덜 정교한 언어로, 7 개의 별개의 기능 콜 프레임이 스택에 배치되어 튀어 나올 수 있습니다.

많은 기능적 언어로 적절하게 쓰여진 계승 기능도 꼬리 재귀가 될 것입니다. 이 경우 언어는 다른 함수 호출을 피하기 위해 단순히 함수의 하단에서 상단으로 점프하도록 선택할 수 있습니다. 이 경우 언어는 재귀 함수를 "무료로"루프로 전환합니다.

Answer 2

그것은 당신이 재귀 요인 기능에 대해 이야기하는 것처럼 들립니다.

int factorial(int n) {
    return n>=1 ? n * factorial(n-1) : 1;
}

이 기능은 스스로 호출됩니다 재귀 적으로 주어진 계승 (N)을 계산하는 데 필요한 시간 수.

대부분의 모든 재귀 함수는 스택을 사용하여 연속 결과를 축적하여 반복 솔루션으로 변환 할 수 있습니다 ...

int factorial(int n) {
    int accu = 1;
    int i;
    for(i = 1; i <= n; i++) {
        accu *= i;
    }
    return accu;
}

Answer 3

할 수 있습니다. 당신이 묻는 것은 메모 화 - 나중에 계산 속도를 높이기 위해 이전 결과를 저장합니다. 예를 들어, 9!를 계산하면 1 값을 1에 저장할 수 있습니다! .. 9! 나중에 저장된 값을 반환 할 수 있습니다. 마찬가지로 10!을 요청하면 10 × 9를 계산할 수 있습니다! 빠르게.

문제는 그 계승입니다 (N) 큰 값을 위해 너무 빨리 자랍니다 N 많은 스토리지를 사용할 수 있으므로 시공간 거래는 가치가 없을 수 있습니다.

Memoization을 효과적으로 사용할 수있는 또 다른 기능은 Fibonacci 번호를 계산하는 것입니다.