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.)
1 << n
can't overflow. This seems to be an exercise in inventing a way to decompose(1<<n) - 1
into multiple steps, perhaps setting each bit one at a time like some answers show.def fn(n): if n == 0: return 1; return (2 << n) - fn(0); # technically recursive
C:\MyFolder