Напишите рекурсивную функцию binary_power() для проверки, является ли переданное натуральное число степенью двойки. Если не является, функция возвращает False, иначе - степень.

Привет! Давай разберемся с этой задачей.

Нам нужно написать рекурсивную функцию binary_power(n), которая проверяет, является ли число n степенью двойки. Если да, то возвращает саму степень (например, для 8 вернет 3, потому что 2³ = 8). Если нет, то возвращает False.

Логика решения:

• Базовый случай 1: Если число n равно 1, это 2⁰, так что степень — 0.
• Базовый случай 2: Если число n меньше 1 (или равно 0), оно точно не является натуральной степенью двойки, поэтому возвращаем False.
• Рекурсивный шаг: Если число n четное (делится на 2 без остатка), то мы можем разделить его на 2 и рекурсивно вызвать функцию для n / 2. К результату этого вызова добавим 1 (так как мы поделили на 2, увеличивая степень на 1).
• Если число нечетное: Если на каком-то шаге число оказывается нечетным (и не равным 1), значит, оно не является степенью двойки. Возвращаем False.

Пример 1: binary_power(1024)

• 1024 четное, вызываем binary_power(512) + 1
• 512 четное, вызываем binary_power(256) + 1 + 1
• ...
• 8 четное, вызываем binary_power(4) + 1 + 1 + 1 + 1 + 1 + 1 + 1
• 4 четное, вызываем binary_power(2) + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
• 2 четное, вызываем binary_power(1) + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
• binary_power(1) возвращает 0.
• Итого: 0 + 10 = 10.

Пример 2: binary_power(42)

• 42 четное, вызываем binary_power(21) + 1
• 21 нечетное и не равно 1, поэтому binary_power(21) возвращает False.
• Итого: False + 1 = False.

Код на Python:

def binary_power(n): 
    if n == 1:
        return 0
    if n < 1 or n % 2 != 0:
        return False
    
    result = binary_power(n / 2)
    
    if result is False:
        return False
    else:
        return result + 1

Ответ:

• Пример 1: print(binary_power(1024)) выведет 10
• Пример 2: print(binary_power(42)) выведет False