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

by

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

Leave a Comment