Mfcttrf

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

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"

2**n -1 is also 1+2+4+...+2^n-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.)

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

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

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