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

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"

Solution 1:

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

Solution 2:

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

Solution 3:

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