50

I need a function that takes n and returns 2n - 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"

13
  • 4
    Just for the record, it should be vastly more efficient to do it like a normal person with a shift and subtract. Python integers are arbitrary width so 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. Oct 14, 2019 at 23:57
  • 8
    def fn(n): if n == 0: return 1; return (2 << n) - fn(0); # technically recursive
    – MooseBoys
    Oct 15, 2019 at 6:28
  • 3
    @Voo: Not Carl, but please list me everything that is contained in C:\MyFolder
    – Flater
    Oct 16, 2019 at 11:11
  • 1
    @Voo: Dependency or not is irrelevant for an exercise which purely focuses on teaching the concept of recursion. I could make a basic mocked set of classes/methods that students could use. You're focusing on something that is completely besides the point of the exercise. Using file system navigation is a good example because students generally understand the inherently recurrent nature of folders and files (i.e. folders can be nested in each other nigh indefinitely)
    – Flater
    Oct 16, 2019 at 11:47
  • 1
    @Voo No I'm saying that you can teach recursion by showing a recursive data structure. I have no idea why you struggle grasping this.
    – Flater
    Oct 16, 2019 at 21:46

7 Answers 7

55

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

12
  • 4
    but required_steps(0) now causes infinite recursion
    – Mulan
    Oct 14, 2019 at 14:17
  • 7
    2^0 - 1 == 0. Add another if for that case.
    – h4z3
    Oct 14, 2019 at 14:18
  • 9
    @user633183 Yes, I know what a total function is. Do you? Because it won't ever be a total function. Nor are the other answers total functions. And yes, more code would be needed to make them total functions. - As I said, we have no domain. What should we assume our domain is? Even if it's just int, we don't know what to do when n<0. Calculate? Throw an error? Return 0? In this case, we only can do a partial function (define it for things we know what the result is).
    – h4z3
    Oct 14, 2019 at 14:39
  • 4
    The base case in the OP’s code is 0 and uses n - 1 for the subproblem. A domain of Natural Numbers seems like a good fit.
    – Mulan
    Oct 14, 2019 at 14:47
  • 4
    Thank you so much! In my humble opinion, this is the best solution for my specific problem. I didn't state possible values for n, really sorry! I know that is kinda important... the exercise states: "You can assume that the parameter n is always a positive integer and greater than 0"
    – Kajice
    Oct 14, 2019 at 15:40
36

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
0
9

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
0
0

Using an additional parameter for the result, r -

def required_steps (n = 0, r = 1):
  if n == 0:
    return r - 1
  else:
    return required_steps(n - 1, r * 2)

for x in range(6):
  print(f"f({x}) = {required_steps(x)}")

# f(0) = 0
# f(1) = 1
# f(2) = 3
# f(3) = 7
# f(4) = 15
# f(5) = 31

You can also write it using bitwise left shift, << -

def required_steps (n = 0, r = 1):
  if n == 0:
    return r - 1
  else:
    return required_steps(n - 1, r << 1)

The output is the same

5
  • 2
    Unnecessary to involve bitwise operations for a simple multiplication exercise.. not readable at all. Also, no need for the else clause in either function
    – rafaelc
    Oct 14, 2019 at 14:56
  • The only difference is changing r * 2 to r << 1 and that is "not readable at all"? 😂
    – Mulan
    Oct 14, 2019 at 15:46
  • 2
    Inventing a 2nd parameter just turns this into a loop that shifts left n times and then subtracts 1. Seems even less elegant then necessary, although the whole thing is an exercise in inefficiency vs. (1<<n) - 1. Oct 15, 2019 at 1:03
  • 1
    @PeterCordes: Moving the state into an accumulator parameter is the standard way of transforming a recursive call into a tail-recursive call. Now, unfortunately, Python doesn't support Proper Tail Calls, not even Proper Tail Recursion, but that doesn't mean that this isn't a useful technique to learn so that you can apply it in other languages that do implement Proper Tail Calls or at least Proper Tail Recursion. Oct 15, 2019 at 3:10
  • 1
    @JörgWMittag Yes, but in this case it's hard to disguise the fact that it would be more natural as a loop. Maybe it's just that I spend so much time on assembly language and performance, but writing a "loop" by using tail-recursion seems pointless in an imperative language when you could just write a loop. Or perhaps what bothers me about this answer is just the choice of how to decompose: into one-at-a-time shifts and then a final subtract as the basecase. Probably a combination of both. Oct 15, 2019 at 3:21
0

Have a placeholder to remember original value of n and then for the very first step i.e. n == N, return 2^n-1

n = 10
# constant to hold initial value of n
N = n
def required_steps(n, N):
    if n == 0:
        return 1
    elif n == N:
        return 2 * required_steps(n-1, N) - 1
    return 2 * required_steps(n-1, N)

required_steps(n, N)
-1

One way to get the offset of "-1" is to apply it in the return from the first function call using an argument with a default value, then explicitly set the offset argument to zero during the recursive calls.

def required_steps(n, offset = -1):
    if n == 0:
        return 1
    return offset + 2 * required_steps(n-1,0)
-1

On top of all the awesome answers given earlier, below will show its implementation with inner functions.

def outer(n):
    k=n
    def p(n):
        if n==1:
            return 2
        if n==k:
            return 2*p(n-1)-1
        return 2*p(n-1)
    return p(n)

n=5
print(outer(n))

Basically, it is assigning a global value of n to k and recursing through it with appropriate comparisons.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.