How to write 2**n - 1 as a recursive function?
I need a function that takes n and returns 2 n - 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"
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.)