How to understand recursion for binary representation function

Question

I traced the following code, and one part doesn't make sense to me:

def bin_rep(n: int) -> str:
     """Return the binary representation of n
     >>> bin_rep(0)
     "0"
     >>> bin_rep(1)
     "1"
     >>> bin_rep(5)
     "101"
     """

     if n > 1:
         return bin_rep(n // 2) + bin_rep(n % 2)
     else:
         return str(n)

The part that I don't understand is, why are we adding bin_rep(n//2) and bin_rep(n%2). I know that without the addition this won't work, but I can't wrap my head around why the addition exists there.

Since bin_rep always returns a string, this is a string concatenation rather than an addition. Does that help you? — Anthony Labarre
– Anthony Labarre, Commented Aug 14, 2018 at 19:58

Prune · Accepted Answer · 2018-08-14 19:57:44Z

4

That's not addition. bin_rep returns a string. The + operator for type string is concatenation. Read this as

binary representation of n right-shifted a bit
    concatenated with
binary representation of n's right-most bit

Does that clear it up?

answered Aug 14, 2018 at 19:57

Prune

78k14 gold badges63 silver badges83 bronze badges

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

Comments

Mark Tolonen · Accepted Answer · 2018-08-14 19:59:59Z

1

bin_rep(n) returns the binary string representation of n.

The termination condition is n <= 1 which is bin_rep(0) -> '0' or bin_rep(1) -> '1'.

bin_rep(2) must return '10'. To do that it computes:

bin_rep(2 // 2) + bin_rep(n % 2)
bin_rep(1) + bin_rep(0)
'1' + '0'  # String concatenation, not decimal addition!
'10'

... which is the correct answer. That should help clear up your understanding.

answered Aug 14, 2018 at 19:59

Mark Tolonen

181k26 gold badges183 silver badges279 bronze badges

1 Comment

crescent Over a year ago

Thank you very much, that helped me out a lot!

Collectives™ on Stack Overflow

How to understand recursion for binary representation function

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related