Program that calculates binary gap using recursion in python generates recursion error

user_19573691 0
Viewed 45

I am new at programming (please be nice :)) and I am trying to write a function that calculates the binary gap of a number using recursion by using the modulus function to gather the bits of an integer and then counting the number of 0s between 1s and displaying the longest chain 0s in between two 1s.

For example

Input = 10, Binary value = 1010, Binary Gap = 1
Input = 15, Binary value = 1111, Binary Gap = 0
Input = 41, Binary value = 101001, Binary Gap = 2

As it stands the code below will always return a 0 if an even number is inputted and always throw a recursion error should an odd number be used. This leads me to believe there is a problem involving the division and it being stuck in an infinite loop but cannot figure out why.

def binary_gap(n, foundFirstOne= False, numofZeros= 0):
if n == 0:
    return 0
bit = n % 2
if bit == 1:
    ans = binary_gap((n / 2), True, 0)
else:
    if foundFirstOne == True:
        ans = binary_gap((n / 2), True, numofZeros+1)
    else:
        ans = binary_gap((n / 2), False, 0)
return ans and numofZeros
print(binary_gap(int(input("Please enter a number"))))
recursion python
4 Answers

First, write a recursive function to convert decimal to binary (not necessary because there is already a bin function). Then, count the gap - there is no point using recursion in this because it is just way too complicated:

def convert_to_binary(n):
    if n > 1:
        return convert_to_binary(n // 2) + str(n % 2)
    return str(n % 2)

def binary_gap(n):
    b = convert_to_binary(n)
    x = b.split('1')[:-1]
    return max(len(d) for d in x)

print(binary_gap(10)) # 1
print(binary_gap(15)) # 0
print(binary_gap(41)) # 2
user_187469590

Besides the code indentation problems, it's too convoluted to use recursion to get this problem. Rather you can use simple strip() and logic like this:

>>> def gap(n):
    ''' find the num's binary gap'''
    sn = bin(n)[2:].strip('0').split('1')
    print(sn)   # just to confirm. can comment out
    return max(len(s) for s in sn)

>>> gap(105); gap(120); gap(121); gap(15)
['', '', '0', '00', '']
2
['', '', '', '', '']
0
['', '', '', '', '00', '']
2
['', '', '', '', '']
0
user_107607680

In your code, you return a value from the function in 2 cases:

  1. n == 0
  2. the function has reached its last line (return ans and numOfZeroes)

In the second case, you call binary_gap again before returning anything. This means that binary_gap will be repeatedly called until n == 0 in one of the function calls, which is when it will stop recursing. However, in no scenario will your function be called with n == 0 unless if 0 is the initial input for n! This is why your function infinitely recurses.

Rather than changing the recursive approach, this can be solved without recursion using much easier techniques. The builtin bin function converts to binary:

n = bin(n)
n = str(n)
n = n[2:]

We convert to a string so we can deal with individual digits and we slice from the 2nd digit onward because all python binary digits start with "0b" before the actual binary digit.

Then simply count the longest repeated 0s:

n = n.split("1")
print(max([len(zeroSet) for zeroSet in n]))
user_195634680

To answer the actual question that was asked, why is this experiencing infinite recursion?

Here is your code with a little extra:

def binary_gap(n, foundFirstOne= False, numofZeros= 0, depth=0):
    print(f"recursion depth {depth}, n is {n}")
    if n < 0.001:
        print ("I think we've made our point. Use integer division.")
        return 0
    
    if n == 0:
        return 0
    bit = n % 2
    if bit == 1:
        ans = binary_gap((n / 2), True, 0)
    else:
        if foundFirstOne == True:
            ans = binary_gap((n / 2), True, numofZeros+1, depth+1)
        else:
            ans = binary_gap((n / 2), False, 0, depth+1)
    return ans and numofZeros

binary_gap(1)

recursion depth 0, n is 1
recursion depth 0, n is 0.5
recursion depth 1, n is 0.25
recursion depth 2, n is 0.125
recursion depth 3, n is 0.0625
recursion depth 4, n is 0.03125
recursion depth 5, n is 0.015625
recursion depth 6, n is 0.0078125
recursion depth 7, n is 0.00390625
recursion depth 8, n is 0.001953125
recursion depth 9, n is 0.0009765625
I think we've made our point. Use integer division.

Compare these in an interpreter:

1 / 2  
> 0.5  
1 // 2  
> 0

I'd be happy to comment more about how to do this effectively in python, using modulo two arithmetic, if requested.

user_17665440
Related