考虑两个函数，它们接受无符号整数作为参数并返回该数字的位数。一个函数是递归的，另一个是非递归的。
就复杂度而言，哪种实现更好？
使用的语言是 C/C++。
这是非递归函数：
int nbOfDigitsNR(int nb) {
int i=0
while(nb!=0){
nb=nb/10;
++i;
}
return i; // i is the number of digits
}
递归函数：
int nbOfDigitsNR(int nb) {
static int i;
if (nb!=0){
i=i+1;
nbOfDigitsNR(nb/10);}
return i;
}
我建议时间复杂度是相同的：O（n），空间复杂度不同：O（n） 递归。O（1） 非递归。
如果一个解决方案是递归的，另一个是迭代的，那么时间复杂度应该是相同的，当然这是相同的算法实现两次 - 一次递归和一次迭代。
区别在于空间复杂性以及编程语言（在您的情况下C++如何处理递归）。
您的示例正好说明了这一点。这两个函数将具有相同的时间复杂度，而递归函数将具有更大的空间复杂度，因为C++为堆栈上的每个递归调用分配变量。
您对时间和空间的复杂性是正确的，如果 n 表示位数。如果 n 表示整数，则用 lg（n） 替换它。
说一个函数是递归的或非递归的并不能告诉我们它的复杂性。
它可以相等，也可以是复杂度较低的其中一个......这完全取决于算法。
我有一辆蓝色和一辆灰色的车。哪一个更快？