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

recursion

Question

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"

Answer 1

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.

Answer 2

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, dado que f(n) = 2 * f(n - 1) + 1 , puede 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

Answer 3

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

Answer 4

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

Answer 5

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)

Answer 6

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 bit a 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

Answer 7

2**n -1 también es 1 + 2 + 4 + ... + 2 ^n-1 que puede convertirse en una sola función recursiva (sin que la segunda reste 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 se garantiza que n 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).