Как написать 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»

47
задан selbie 14 October 2019 в 19:39
поделиться

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)

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

52
ответ дан 7 November 2019 в 13:15
поделиться

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

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

, вывод - тот же

0
ответ дан 7 November 2019 в 13:15
поделиться

Имейте заполнителя, чтобы помнить исходное значение 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)
0
ответ дан 7 November 2019 в 13:15
поделиться

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

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
ответ дан 7 November 2019 в 13:15
поделиться

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

def required_steps(n, offset = -1):
    if n == 0:
        return 1
    return offset + 2 * required_steps(n-1,0)
-1
ответ дан 7 November 2019 в 13:15
поделиться
Другие вопросы по тегам:

Похожие вопросы: