Не знаете, что возвращает эта рекурсивная функция

Question

Я читаю о рекурсивных функциях, и я пытаюсь выяснить математическую формулу для этого. Я подумал, что это логарифмическая функция, но, похоже, это не так. Если бы кто-нибудь мог указать мне в правильном направлении, я был бы признателен.

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

    return 1 + f(n/2); 
} 

Answer 1

Эта функция возвращает число раз функция выполняется путем деления целого числа на 2 до достижения нулевого

EX:

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 2

Поскольку вы обеспокоены математической формулой, что функция основана на:

Здесь находится: 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) (base 2) шагов, чтобы достичь 1, следовательно, это логарифмическая сложность с O(logn).

Answer 3

Более точно, это реализует пол (logbase2 (п))

Answer 4

Это функция логарифм, просто к основанию 2. Более конкретно, это ceil1 + floor(log2(n)).

Answer 5

Я знаю, что вы сказали, «Математическая функцию», и это установить перспективу для существующих ответов, но, чтобы показать другую точку зрения, она возвращает:

• количества бит, необходимых для хранения n (если учесть, 1 биты необходимо осмысленно кодируют число 0, отличную от без номера вообще)
• 1 на основе индекса наиболее значащим битом, установленным в n|1, он же
• минимум (1) и (1 на основе индекса наиболее значимых бит установлен в в n)

Иногда, когда вы смотрите на код, это может помочь увидеть, что функция может использоваться с разными намерениями - любая перспектива может облегчить понимание контекста использования.