0

For a class in uni, I am required to write a function that recursively converts binary strings to its decimal representation.

The code that I wrote is as below:

def bin_to_dec(b):
    """takes an input of a string 'b' representing a 
    binary number and then returns its decimal representation"""
    if b == 0:                #base case 1: when n is 0 
        return "0"
    elif b == 1:              #base case 2: when is n is 1
        return "1"
    else:                     #recursive case
        bin_to_dec_rest = bin_to_dec(b[1:])
        dec_value = int(b[0])*2 + bin_to_dec_rest
        return dec_value

Upon doing so, I got the following error in my console: Recusion error

Could someone please explain what this means, and why it may have occurred?

Urvi Chakravarthy
  • 1
  • 1
  • I did a simple google search on your error - did you not try that? – mgillett Jul 16 '23 at 12:16
  • According this (https://stackoverflow.com/questions/5061582/setting-stacksize-in-a-python-script) and this (https://stackoverflow.com/questions/3323001/what-is-the-maximum-recursion-depth-and-how-to-increase-it), the recursion limit is at 1000. What is your "string" `b` like? And why do you use integer comparison `b==0`? In case `b` is a string you should compare `b=="0"`. – destructioneer Jul 16 '23 at 12:19

1 Answers1

0

Python has a maximum recursion level (1000, from memory(1)) which you can change but I'm not convinced that will fully help here.

The fact that b is a string means that if b == 0 will never be true.

You should be comparing strings with strings, not with integers.

(1) This means it will fail if your binary strings are longer than about a thousand bits (taking into account any stack that's in use before you start recursion) but, to be honest, recursion is not really a good fit here. It's best left for scenarios with the problem space reduced quickly (like a binary search where it halves at each recursion level).

And yes, I realise that's a requirement of the assignment. So, if it is needed because of that, you can use something like sys.setrecursionlimit(2000) to change it, but there are risks in doing that.

paxdiablo
  • 854,327
  • 234
  • 1,573
  • 1,953