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

From: stackoverflow.com/q/58378549