Turning a while loop to a recursion

Question

I'm trying to turn this code ( that gives the maximum number of consecutive 0's in a binary) to a recursive code. I tried in many ways but the result is wrong. This is the code using a while loop :

def consecutivezeros(N):
    if N==0 :
        return 1
    # variable to store the length
    # of longest consecutive 0's
    maxm = -1

    # to temporary store the
    # consecutive 0's
    cnt = 0
    while (N):
        if (not (N & 1)):
            cnt += 1
            N >>= 1
            maxm = max(maxm, cnt)
        else:
            maxm = max(maxm, cnt)
            cnt = 0
            N >>= 1

    return maxm

I dont think that recursion can be of use in this method. that path your code is following is linear, and so recursion won't fit nicely to solve it. why do you want to use recursion? — idik
– idik, Commented Feb 23, 2021 at 9:42
A better naming scheme could go a long way in making this easier to rewrite. Is N an input number? Is maxm the maximum_count, and cnt the current_count? In how far have you "tried in many ways but the result is wrong."? — MisterMiyagi
– MisterMiyagi, Commented Feb 23, 2021 at 9:52
@idik Google "tail recursion", which is likely the intended outcome of this exercise. — user4815162342
– user4815162342, Commented Feb 23, 2021 at 9:59
i have to use recursion for an exercise , i have to write ONE function that takes a integer N and have to return the the maximum number of consecutive 0's in the binary form of N. And it have to be done in a recursive way :/ — kr4t0s26
– kr4t0s26, Commented Feb 23, 2021 at 10:08

juanpa.arrivillaga · Accepted Answer · 2021-02-23 20:11:15Z

1

Here is the principled way:

def consecutivezeros(N):
    if N == 0:
        return 1
    def _consecutivezeros(N, maxm, cnt):
        if not N:
            return maxm
        elif (not (N & 1)):
            new_cnt = cnt + 1
            return _consecutivezeros(N>>1, max(maxm, new_cnt), new_cnt)
        else:
            return _consecutivezeros(N>>1, max(maxm, cnt), 0)
    return _consecutivezeros(N, -1, 0)

Here is the dumb, unprincipled way, basically just use a recursive helper function that mutates variables in it's closure, this is just to demonstrate how recursion can basically replace a while-loop directly, but it's not very elegant:

def consecutivezeros(N):
    if N == 0:
        return 1
    maxm = -1
    cnt = 0
    def _looper():
        nonlocal maxm, cnt, N
        if not N:
            return
        if (not (N & 1)):
            cnt += 1
            maxm = max(maxm, cnt)
        else:
            maxm = max(maxm, cnt)
            cnt = 0
        N >>= 1
    _looper(N)
    return maxm

EDIT:

If you don't want to use an auxilliary helper function, you need additional arguments:

def consecutivezeros(N, _maxm=-1, _cnt=0, _first=True):
    if N == 0 and _first:
        return 1
    elif not N:
        return _maxm
    elif (not (N & 1)):
        incr = _cnt + 1
        return consecutivezeros(N>>1, max(_maxm, incr), incr, False)
    else:
        return consecutivezeros(N>>1, max(_maxm, _cnt), 0, False)

edited Feb 23, 2021 at 20:11

answered Feb 23, 2021 at 9:47

juanpa.arrivillaga

97.6k14 gold badges141 silver badges190 bronze badges

Sign up to request clarification or add additional context in comments.

12 Comments

kr4t0s26 Over a year ago

the principled way works with the examples I have but does not work with N = 0 , 4 or 2 ,

kr4t0s26 Over a year ago

another thing is that the exercise says that we don't have the right to create another function :/

juanpa.arrivillaga Over a year ago

@kr4t0s26 yeah it had a bug, it should work now

juanpa.arrivillaga Over a year ago

@kr4t0s26 well, you can still do it, but then your function need additional arguments, it's just cleaner to do it with a little helper function like that so as not to expose arguments that are implementation details and not really part of the API

kr4t0s26 Over a year ago

right , they insisted on the fact that we can add as many arguments as we want to our function

|

jån · Accepted Answer · 2021-02-23 10:16:58Z

0

def rec_count(s: str, c: int = 0, m: int = 0):
    if s:
        if s[0] == "0":
            if (c := c+1) > m:
                m = c

            return rec_count(s[1:], m=m, c=c)
        else:
            return rec_count(s[1:], m=m)
    else:
        return m


N = 100000100101
print(rec_count(s=str(N)))
# 5

EDIT: According to comment, input is int instead of binary or str. Changed solution accordingly.

edited Feb 23, 2021 at 10:16

answered Feb 23, 2021 at 9:42

jån

1531 silver badge9 bronze badges

3 Comments

jån Over a year ago

I just noticed, that I overread your mention of "consecutive 0s".

kr4t0s26 Over a year ago

im sorry i didn't say this in my question : the N is an integer number not a binary one

jån Over a year ago

You can transform an int into a str with N_as_string = str(N). EDIT: Added it to the original function.

Mulan · Accepted Answer · 2021-02-24 06:18:44Z

Recursion is a functional heritage and so using it with functional style yields the best results. This means avoiding things like mutations, variable reassignments and other side effects. We can use inductive reasoning to solve the problem in a principled way -

If the input, n, has only a single bit, the base case has been reached. Return the zero streak, z, if n is 1 or return z plus 1 for the final zero
(inductive) n has more than one bit remaining. If the first bit is a 1, the streak is broken. Yield the current zero streak, z, and recur on the sub-problem n >> 1 with a fresh zero streak of 0
(inductive) n has more than one bit and the first bit is a 0. Recur on the sub-problem n >> 1 with an incremented zero streak

def consecutive_zeroes(n, z = 0):
  if n < 2:                                      # 1
    yield z if n == 1 else z + 1
  elif n & 1:                                    # 2
    yield z
    yield from consecutive_zeroes(n >> 1, 0)
  else:                                          # 3
    yield from consecutive_zeroes(n >> 1, z + 1)

Notice the generator is disentangled from the max logic. The built-in max function already accepts an iterable input, so there's little sense in duplicating that.

for x in range(20):
  print(f"{x:b}", max(consecutive_zeroes(x)))

for x in range(60, 80):
  print(f"{x:b}", max(consecutive_zeroes(x)))

for x in range(500, 520):
  print(f"{x:b}", max(consecutive_zeroes(x)))

111110100 2
111110101 1
111110110 1
111110111 1
111111000 3
111111001 2
111111010 1
111111011 1
111111100 2
111111101 1
111111110 1
111111111 0
1000000000 9
1000000001 8
1000000010 7
1000000011 7
1000000100 6
1000000101 6
1000000110 6
1000000111 6

prevent leaked parameters

If you don't want extra parameters like z or expecting caller to require max, we can embed a nested helper, loop, in our function -

def consecutive_zeroes(n):          # <- new wrapper, with no leaked parameters
  def loop(n, z):                   # <- our function above, renamed to loop
    if n < 2:
      yield z if n == 1 else z + 1
    elif n & 1:
      yield z
      yield from loop(n >> 1, 0)
    else:
      yield from loop(n >> 1, z + 1)
  return max(loop(n, 0))            # <- max

Now when you call it, max is no longer required by the caller -

for x in range(20):
  print(f"{x:b}", consecutive_zeroes(x))   # <- no need to call max

# ...

related Q&A

How to find all numbers in a range without consecutive zeroes

Collectives™ on Stack Overflow

Turning a while loop to a recursion

3 Answers 3

12 Comments

3 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

12 Comments

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related