이 기능으로 인해 segfault가 발생하는 이유는 무엇입니까?

Question

모듈화 된 지수 계산을 수행하기 위해 다음과 같은 간단한 함수를 작성했습니다. 그러나 지수 매개 변수가 약 261,000보다 클 때 오류가 발생합니다. 왜 이런거야? 어떻게 해결할 수 있습니까?

64 비트 우분투에서 gcc로 컴파일 중입니다.

감사

는

unsigned int modex(unsigned int base, unsigned int exponent, unsigned int modulus) 
{ 
    if(exponent == 1) 
     return base; 

    base = base % modulus; 

    if(exponent == 0 || base == 1) 
     return 1; 

    return (modex(base, exponent - 1, modulus) * base) % modulus; 
} 

Answer 1

@ouah는 이미 답변에 답변을 게시 했으므로 답변을 게시하려면이 항목을 삭제하겠습니다.

스택 오버플로가 있습니다. 당신은 너무 많은 시간을 반복하고 스택 공간을 불고 있습니다. C++은 꼬리 호출 최적화를 보장하지 않습니다 (최종 호출의 반환 값에 대해 해당 연산을 수행하지 않았더라도). 따라서 루프를 사용하여 구현하는 것이 좋습니다.

재귀 경로를 계속 사용하려면 here 설명을 통해 실제로 꼬리 재귀를 만들고 컴파일러가 도움이되는지 확인하십시오.

Answer 2

귀하의 재귀는 전체 자루를 차지 너무 깊은된다. 대신 while 루프를 사용해보십시오.

Answer 3

엄청난 재귀 체인을 만듭니다. 메모리와 프로세스를 반복적으로 수행하여 메모리를 절약하고 처리해야합니다.

unsigned modex(unsigned base, unsigned exponent, unsigned modulus){ 

    unsigned 
     result = 1; 

    while(expoent--){ 
     result *= base; 
     result %= modulus; 

    } 

    return result; 

} 

그래도 더 빨리 처리 할 수 ​​있습니다.