Предположения, сделанные в этом ответе:
sum объявлено глобально - поскольку явно отсутствующее объявление, как вы заявили, не является опечаткой. - Вопрос требуетвозвращаемое значение, а не сложность по времени.
- Выражения в выражении возврата оцениваются в порядке их появления;это не гарантируется стандартом C, поэтому ответ технически не определен.
Обратите внимание, что, поскольку каждый вызов выполняет одно из следующих действий:
- Возвращает свой аргумент (if
n <= 1) - Сбрасывает значение
sum в 0
... функция гарантированно будет закрыта, в том смысле, что ее возвращаемое значение будет только зависит от его аргумента.Отсюда следует, что:
Два отдельных вызова на Recursive(n / 2) могут быть объединены в один вызов, не влияя на возвращаемое значение: return 2 * Recursive(n / 2) + sum;.
Из этогоСчитается, что эта модификация была применена к исходному коду;это помогает уточнить ход выполнения программы, поскольку теперь будет только один путь выполнения (вместо ветвей, созданных двумя вызовами).
Теперь для ключевой части.Вызов Recursive(n / 2) перезаписывает значение sum перед возвратом функции, отменяя работу, выполненную предыдущим циклом for.Это перезаписывающее поведение продолжается по иерархии рекурсии, до последнего вызова, когда выполняется условие остановки n <= 1 (вместо этого возвращается просто n).Из этого следует, что:
Существует только одно значение sum, которое вносит вклад в окончательное возвращаемое значение, определяемое его значением после предпоследнего вызовадо Recursive.
Из-за усечения целочисленным делением, когда выполняется предпоследний вызов n равен всегда 2 или 3 (оба из которых удовлетворяют n / 2 = 1);таким образом, это также возможные окончательные значения sum.
Какие значения n дают sum = 2 и sum = 3 соответственно?Иллюстративно рассмотреть двоичное представление n.
Целочисленное деление на 2 эквивалентно сдвигу битового набора «вправо» на 1 (или «влево» в зависимости от порядкового номера ...) и отбрасыванию младшего значащего бита.Из этого следует, что окончательное значение sum зависит только от 2 старших значащих битов n:
initial bit-pattern >> penultimate call
-----------------------------------------
...000 10 xxx... ...0000 10 = 2
...000 11 xxx... ...0000 11 = 3
xxx: discarded bits
Битовая последовательность n имеет floor(log2(n)) + 1значимые биты;итоговое значение sum может поэтому быть кратко выражено как:
S(n) = 2 + second_most_significant_bit(n)
Сколько раз sum добавляется к возвращаемому значению?Число рекурсивных звонков на Recursive (т. Е. Общее количество звонков минус один, включая начальный звонок, но исключая последний).Это задается как floor(log2(n)):
Обратите внимание, что возвращаемое значение последнего вызова будет всегда быть 1если изначально n >= 1.Поэтому окончательное возвращаемое значение Recursive определяется следующим образом:
Проверка кода C для подтверждения:
// override the library definition of log2 to use integers only
int log2(int n) {
int b = 0;
while ((n >>= 1) != 0)
b++;
return b;
}
// get i-th bit from bit pattern of n
int get_bit(int n, int i) {
return (n >> (i - 1)) & 1;
}
// calculating return value of Recursive using equation above
int Value(int n) {
int l2n = log2(n); // floor(log2(n))
int p2l = 1 << l2n; // 2^(floor(log2(n)))
return p2l + (p2l - 1) * (2 + get_bit(n, l2n));
}
Результаты:
n | Recursive Value
-------------------------------
2 | 4 4
3 | 5 5
4 - 5 | 10 10
6 - 7 | 13 13
8 - 11 | 22 22
12 - 15 | 29 29
16 - 23 | 46 46
24 - 31 | 61 61
32 - 47 | 94 94
48 - 63 | 125 125
64 - 95 | 190 190