¿Cómo escribir 2 ** n - 1 como una función recursiva?

Necesito una función que tome n y devuelva 2 ⁿ - 1 . Suena bastante simple, pero la función tiene que ser recursiva. Hasta ahora solo tengo 2 ⁿ :

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

El ejercicio dice: "Se puede suponer que el parámetro n es siempre un número entero positivo y mayor que 0"

2**n -1también es 1 + 2 + 4 + ... + 2 ^n-1 que puede convertirse en una única función recursiva (sin la segunda para restar 1 de la potencia de 2).

Sugerencia : 1 + 2 * (1 + 2 * (...))

Solución a continuación, no busque si desea probar la pista primero.

Esto funciona si nse garantiza que es mayor que cero (como se prometió en la declaración del problema):

def required_steps(n):
    if n == 1: # changed because we need one less going down
        return 1
    return 1 + 2 * required_steps(n-1)

Una versión más robusta también manejaría valores cero y negativos:

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)

(Agregar un cheque para los no enteros se deja como ejercicio).

Para resolver un problema con un enfoque recursivo, tendría que averiguar cómo puede definir la función con una entrada dada en términos de la misma función con una entrada diferente. En este caso, desde entonces f(n) = 2 * f(n - 1) + 1, puedes hacer:

def required_steps(n):
    return n and 2 * required_steps(n - 1) + 1

así que eso:

for i in range(5):
    print(required_steps(i))

salidas:

0
1
3
7
15

Puedes extraer la parte realmente recursiva a otra función

def f(n):
    return required_steps(n) - 1

O puede establecer una bandera y definir cuándo sustraer

def required_steps(n, sub=True):
    if n == 0: return 1
    return 2 * required_steps(n-1, False) - sub

>>> print(required_steps(10))
1023

Usando un parámetro adicional para el resultado, 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

También puede escribirlo usando el desplazamiento a la izquierda a nivel de bit, <<-

def required_steps (n = 0, r = 1):
  if n == 0:
    return r - 1
  else:
    return required_steps(n - 1, r << 1)

La salida es la misma

Tenga un marcador de posición para recordar el valor original de n y luego para el primer paso n == N, es decir , regresar2^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)

Una forma de obtener el desplazamiento de "-1" es aplicarlo en el retorno de la primera llamada de función utilizando un argumento con un valor predeterminado, luego establecer explícitamente el argumento de desplazamiento en cero durante las llamadas recursivas.

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

Además de todas las increíbles respuestas dadas anteriormente, a continuación se mostrará su implementación con funciones internas.

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))

Básicamente, está asignando un valor global de n a k y recurriendo a través de él con las comparaciones apropiadas.