Как написать 2 ** n - 1 как рекурсивную функцию?

Мне нужна функция, которая принимает n и возвращает 2 ⁿ - 1. Это звучит достаточно просто, но функция должна быть рекурсивной. Пока у меня есть только 2 ⁿ:

def required_steps(n):
    if n == 0:
        return 1
    return 2 * req_steps(n-1)

В упражнении говорится: "Можно предположить, что параметр n всегда является положительным целым числом и больше 0"

Ответ 1

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)

(Добавление проверки на нецелые числа оставлено в качестве упражнения.)

Ответ 2

Чтобы решить проблему с рекурсивным подходом, вы должны выяснить, как вы можете определить функцию с заданным входом в терминах той же функции с другим входом. В этом случае, начиная с 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))

выходы:

Ответ 3

Вы можете извлечь действительно рекурсивную часть в другую функцию

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

Ответ 4

Иметь заполнитель для запоминания исходного значения 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)

Ответ 5

Используя дополнительный параметр для результата, 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)

Выход такой же

Ответ 6

Я думаю об этом, пытаясь выразить f (n + 1) через f (n). Следовательно,

f (n + 1) = 2 ^ (n + 1) - 1 = 2 * (2 ^ n) - 1 = 2 * (2 ^ n - 0,5) = 2 * (2 ^ n - 1 + 0,5) = 2 * (2 ^ n - 1) + 1 = 2 * f (n) + 1.

Ваш код будет:

def required_steps(n):
    if n == 0:
        return 0
    return 2 * required_steps(n-1) + 1

Ответ 7

Один из способов получить смещение "-1" - применить его в возвращении первого вызова функции, используя аргумент со значением по умолчанию, а затем явно установить нулевой аргумент смещения во время рекурсивных вызовов.

def required_steps(n, offset = -1):
    if n == 0:
        return 1
    return offset + 2 * required_steps(n-1,0)

Ответ 8

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

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 и повторяется через него с соответствующими сравнениями.