c++ - 不确定这个递归函数返回什么

Question

我正在阅读有关递归函数的信息，并且一直试图找出这个函数的数学公式。我想也许它是一个对数函数，但似乎不是这样。如果有人能指出我正确的方向，我将不胜感激。

unsigned f(unsigned n){
    if(n<2)
    return 1;

    return 1 + f(n/2);
}

Answer 1

它是一个以 2 为底的对数函数。更具体地说，它是.ceil 1 + floor(log2(n))

Answer 2

我知道您说的是“数学函数”，这为现有答案设定了视角，但为了展示另一个视角，它返回：

• 需要存储的位数n（如果您认为需要 1 位来有意义地编码数字 0 与根本没有数字不同）
• 中设置的最高有效位的基于 1 的索引n|1，又名
• (1) 和（在 中设置的最高有效位的从 1 开始的索引）的n最小值

有时，当您查看代码时，可以帮助您了解可以以不同的意图使用函数 - 任何一种观点都可能更容易理解使用的上下文。

Answer 3

由于您关心该函数所基于的数学公式：

这里是：f是 的函数n：

f(n) = 1 + f(n/2) if n >=2
f(n) = 1          if n <=1  //n is unsigned so n >=0

考虑到上述公式，底层算法就具有对数复杂度。原因是每一步，它都会减少n一半的大小，并且需要log(n)（以 2 为底）步才能达到 1，因此，它是对数复杂度O(logn)。

Answer 4

此函数通过将整数除以 2 直到达到零来返回函数执行的次数

前任：

f(8)-

return f(4) //continue on
return f(2) //continue on
return f(1) //we know this is 1
return f(2) //now we can do this one, 2
return f(4) //and this one, 3

Answer 5

更准确地说，这实现了 floor(logbase2(n))