c++ 大数递归查找 mod
c++ recursion with big numbers to find mod
您好,在练习递归时,我找到了一个不使用 % 运算符即可找到模数的练习。
所以我写了我的函数,一切正常。
除非我用 5 位或更多数字打数字,否则此功能失败。
而且我不确定是我做错了什么还是因为调用太多而失败了。
如果电话太多,是否正常?函数调用真的会太多吗?如果将来我有一个真正有用的递归函数,我怎样才能防止它发生呢?
因为这对我来说真的没有意义。我做了汉诺塔递归,它从来没有这个问题,无论我想移动多少磁盘。
这是我的函数和两个数字始终为正的前提:
#include <iostream>
using namespace std;
int modulo(int n, int m) {
if (n < m) return n;
else return modulo(n - m, m);
}
int main()
{
int n{ 0 }, m{ 0 };
char check{ 'a' };
do {
cout << "Enter 2 positive integers to calculate their modulo: ";
cin >> n >> m;
if (cin.fail()) {
cerr << "Numbers must be a positive integers. Please try again.\n";
cin.clear(); //clear input stream
cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); //discard any unprocessed characters
}
else if (n < 0 || m <= 0) {
cerr << "Numbers must be positive and second number cannot be zero.\nPlease try again.\n";
}
else {
cout << "n%m = " << n << "%" << m << " = " << modulo(n, m) << endl;
cout << " Try again? (enter 'n' to quit): ";
cin >> check;
}
} while (check != 'n');
}
错误是:
Unhandled exception at 0x00007FF77D5C2793 in GuessNumber.exe:
0xC00000FD: Stack overflow (parameters: 0x0000000000000001,
0x0000006F322F3F30).
对于我试过的数字 40001 % 10,它有效但 44001 % 10 失败了
44001 之后的一切对我来说也都失败了。我没试过其他号码
如果递归太深,程序就会用完堆栈内存。它被称为堆栈溢出。
int modulo(int n, int m)
{
if (n < m) return n;
else return modulo(n - m, m);
}
例如,modulo(1000000, 2)
调用 modulo(999998, 2)
,后者调用 modulo(999996, 2)
,依此类推,直到 modulo(0, 2)
最后有 500001 个活动的 modulo
函数在堆栈上。两个整数、return 地址和一个帧指针,在任何合理的系统上每个函数调用应该至少占用 16 个字节。总共 8 兆字节的堆栈 space,通常超过最大堆栈大小。
每个函数调用都必须等待下一个函数的结果,直到它可以完成计算和return。在 return 之前,堆栈必须保存所有变量、参数和 return 地址。 return 地址是程序中在 return
语句后应恢复的位置。
这些调用会填满堆栈,直到达到最大限制并导致程序崩溃。
在某些情况下,编译器可以将递归转换为循环。在这种情况下,由于递归是在 return
语句处,它可以简单地 goto
到函数的开头,而根本不执行调用。这叫做尾调用优化:
int modulo(int n, int m)
{
start:
if (n < m) return n;
else {
n -= m;
goto start;
}
}
如果您启用优化(clang 或 G++ 中的 -O2,或 Visual C++ 中的发布模式),则不会发生崩溃,因为编译器会创建一个循环而不是递归。为避免崩溃,只需启用优化。
请注意,编译器不需要对此进行优化,也不总是可以。这就是为什么不建议进行如此深的递归。
你递归到4400深度,这是自找麻烦。这里也没有必要,因为你可以用一个循环实现相同的算法:
while (n >= m) n -= m ;
return n ;
您好,在练习递归时,我找到了一个不使用 % 运算符即可找到模数的练习。 所以我写了我的函数,一切正常。 除非我用 5 位或更多数字打数字,否则此功能失败。 而且我不确定是我做错了什么还是因为调用太多而失败了。 如果电话太多,是否正常?函数调用真的会太多吗?如果将来我有一个真正有用的递归函数,我怎样才能防止它发生呢? 因为这对我来说真的没有意义。我做了汉诺塔递归,它从来没有这个问题,无论我想移动多少磁盘。
这是我的函数和两个数字始终为正的前提:
#include <iostream>
using namespace std;
int modulo(int n, int m) {
if (n < m) return n;
else return modulo(n - m, m);
}
int main()
{
int n{ 0 }, m{ 0 };
char check{ 'a' };
do {
cout << "Enter 2 positive integers to calculate their modulo: ";
cin >> n >> m;
if (cin.fail()) {
cerr << "Numbers must be a positive integers. Please try again.\n";
cin.clear(); //clear input stream
cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); //discard any unprocessed characters
}
else if (n < 0 || m <= 0) {
cerr << "Numbers must be positive and second number cannot be zero.\nPlease try again.\n";
}
else {
cout << "n%m = " << n << "%" << m << " = " << modulo(n, m) << endl;
cout << " Try again? (enter 'n' to quit): ";
cin >> check;
}
} while (check != 'n');
}
错误是:
Unhandled exception at 0x00007FF77D5C2793 in GuessNumber.exe: 0xC00000FD: Stack overflow (parameters: 0x0000000000000001, 0x0000006F322F3F30).
对于我试过的数字 40001 % 10,它有效但 44001 % 10 失败了 44001 之后的一切对我来说也都失败了。我没试过其他号码
如果递归太深,程序就会用完堆栈内存。它被称为堆栈溢出。
int modulo(int n, int m)
{
if (n < m) return n;
else return modulo(n - m, m);
}
例如,modulo(1000000, 2)
调用 modulo(999998, 2)
,后者调用 modulo(999996, 2)
,依此类推,直到 modulo(0, 2)
最后有 500001 个活动的 modulo
函数在堆栈上。两个整数、return 地址和一个帧指针,在任何合理的系统上每个函数调用应该至少占用 16 个字节。总共 8 兆字节的堆栈 space,通常超过最大堆栈大小。
每个函数调用都必须等待下一个函数的结果,直到它可以完成计算和return。在 return 之前,堆栈必须保存所有变量、参数和 return 地址。 return 地址是程序中在 return
语句后应恢复的位置。
这些调用会填满堆栈,直到达到最大限制并导致程序崩溃。
在某些情况下,编译器可以将递归转换为循环。在这种情况下,由于递归是在 return
语句处,它可以简单地 goto
到函数的开头,而根本不执行调用。这叫做尾调用优化:
int modulo(int n, int m)
{
start:
if (n < m) return n;
else {
n -= m;
goto start;
}
}
如果您启用优化(clang 或 G++ 中的 -O2,或 Visual C++ 中的发布模式),则不会发生崩溃,因为编译器会创建一个循环而不是递归。为避免崩溃,只需启用优化。
请注意,编译器不需要对此进行优化,也不总是可以。这就是为什么不建议进行如此深的递归。
你递归到4400深度,这是自找麻烦。这里也没有必要,因为你可以用一个循环实现相同的算法:
while (n >= m) n -= m ;
return n ;