How to write 2**n - 1 as a recursive function?

user_12214934 0
Viewed 11401

I need a function that takes n and returns 2n - 1 . It sounds simple enough, but the function has to be recursive. So far I have just 2n:

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

The exercise states: "You can assume that the parameter n is always a positive integer and greater than 0"

recursion python
7 Answers

2**n -1 is also 1+2+4+...+2n-1 which can made into a single recursive function (without the second one to subtract 1 from the power of 2).

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

Solution below, don't look if you want to try the hint first.

This works if n is guaranteed to be greater than zero (as was actually promised in the problem statement):

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

A more robust version would handle zero and negative values too:

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)

(Adding a check for non-integers is left as an exercise.)

user_115160120

To solve a problem with a recursive approach you would have to find out how you can define the function with a given input in terms of the same function with a different input. In this case, since f(n) = 2 * f(n - 1) + 1, you can do:

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

so that:

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

outputs:

0
1
3
7
15
user_68909120

You can extract the really recursive part to another function

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

Or you can set a flag and define just when to subtract

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

>>> print(required_steps(10))
1023
user_25356110

Have a placeholder to remember original value of n and then for the very first step i.e. n == N, return 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)
user_35782890

Using an additional parameter for the result, 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

You can also write it using bitwise left shift, << -

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

The output is the same

user_6331830

One way to get the offset of "-1" is to apply it in the return from the first function call using an argument with a default value, then explicitly set the offset argument to zero during the recursive calls.

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

On top of all the awesome answers given earlier, below will show its implementation with inner functions.

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

Basically, it is assigning a global value of n to k and recursing through it with appropriate comparisons.

user_74474250
Related