这个函数为什么会导致段错误？

问题描述：

我写了下面这个简单的函数来执行模幂运算。但是，当指数参数大于约261,000时，它会发生段错误。为什么是这样？我该如何解决它？这个函数为什么会导致段错误？

我正在使用64位Ubuntu上的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; 
}

你有一个stackoverflow – ouah 2013-03-06 18:51:07

答

@ouah已经在评论中发布了答案，所以如果他想发布答案，我会删除它。

你有堆栈溢出。你正在递归太多次，并且吹出你的堆栈空间。 C++并不保证tail调用优化（即使你没有在最后的递归调用的返回值上执行该操作），所以你最好使用循环来实现它。

如果你想坚持递归路线，试着通过解释here真正的尾递归，看看编译器是否可以帮助你。

我会接受这个，如果ouah今天没有发布答案。非常感谢。 – Richard 2013-03-06 19:05:02

+1，@Richard我不会发表任何答案。 – ouah 2013-03-06 19:05:45

答

你的递归变得如此之深，它占据了整个袋子。考虑使用while循环代替。

答

您正在创建一个巨大的递归链。你应该尝试通过迭代来节省内存和处理。

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

    unsigned 
     result = 1; 

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

    } 

    return result; 

}

不过，你可以做得更快。

这个函数为什么会导致段错误？

相关推荐