Как написать 2 ** n - 1 как рекурсивную функцию?
Мне нужна функция, которая принимает n и возвращает 2 n - 1 . Звучит достаточно просто, но функция должна быть рекурсивной. Пока у меня есть только 2 n :
def required_steps(n):
if n == 0:
return 1
return 2 * req_steps(n-1)
В упражнении говорится: «Можно предположить, что параметр n всегда является положительным целым числом и больше 0»
7 ответов
2**n -1 также 1+2+4 +... +2 <глоток> n-1 , который может превращенный в единственную рекурсивную функцию (без второй для вычитания 1 из питания 2).
Подсказка : 1+2* (1+2* (...))
Решение ниже, не смотрите, если Вы хотите попробовать подсказку сначала.
<час> Это работает, если n, как гарантируют, будет больше, чем нуль (как был на самом деле обещан в проблемном операторе):
def required_steps(n):
if n == 1: # changed because we need one less going down
return 1
return 1 + 2 * required_steps(n-1)
А больше устойчивой версии обработало бы нулевые значения и отрицательные величины также:
def required_steps(n):
if n < 0:
raise ValueError("n must be non-negative")
if n == 0:
return 0
return 1 + 2 * required_steps(n-1)
(Добавление проверки на нецелые числа оставляют как осуществление.)
Для решения проблемы с рекурсивным подходом, необходимо было бы узнать, как можно определить функцию с данным входом с точки зрения той же функции с другим входом. В этом случае, с тех пор f(n) = 2 * f(n - 1) + 1, можно сделать:
def required_steps(n):
return n and 2 * required_steps(n - 1) + 1
так, чтобы:
for i in range(5):
print(required_steps(i))
выводы:
0
1
3
7
15
Можно извлечь действительно рекурсивную часть к другой функции
def f(n):
return required_steps(n) - 1
, Или можно установить флаг и определить как раз в то самое время, когда вычесть
def required_steps(n, sub=True):
if n == 0: return 1
return 2 * required_steps(n-1, False) - sub
>>> print(required_steps(10))
1023
Используя дополнительный параметр для результата, r -
def required_steps (n = 0, r = 1):
if n == 0:
return r - 1
else:
return required_steps(n - 1, r * 2)
for x in range(6):
print(f"f({x}) = {required_steps(x)}")
# f(0) = 0
# f(1) = 1
# f(2) = 3
# f(3) = 7
# f(4) = 15
# f(5) = 31
можно также записать это с помощью поразрядного сдвига влево, << -
def required_steps (n = 0, r = 1):
if n == 0:
return r - 1
else:
return required_steps(n - 1, r << 1)
, вывод - тот же
Имейте заполнителя, чтобы помнить исходное значение n и затем для самого первого шага т.е. n == N, возвратиться 2^n-1
n = 10
# constant to hold initial value of n
N = n
def required_steps(n, N):
if n == 0:
return 1
elif n == N:
return 2 * required_steps(n-1, N) - 1
return 2 * required_steps(n-1, N)
required_steps(n, N)
Вдобавок ко всем потрясающим ответам, данным ранее, ниже покажет его реализацию с внутренними функциями.
def outer(n):
k=n
def p(n):
if n==1:
return 2
if n==k:
return 2*p(n-1)-1
return 2*p(n-1)
return p(n)
n=5
print(outer(n))
В основном, это присваивает глобальное значение n к k и рекурсивно вызывает через него с соответствующими сравнениями.
Один способ получить смещение "-1" состоит в том, чтобы применить его в возврате из первого вызова функции с помощью спора со значением по умолчанию, затем явно обнулить аргумент смещения во время рекурсивных вызовов.
def required_steps(n, offset = -1):
if n == 0:
return 1
return offset + 2 * required_steps(n-1,0)