How to recursively increment a binary number (in list form) without converting to integer?

Question

For instance, given list [1, 0, 1] the code would return [1,1,0]. Other examples:

[1,1,1] -- > [1,0,0,0]
[1,0,0,1] --> [1,0,1,0]

I'm having most trouble understanding what my base case for recursion would be and then how to implement for the (n-1) case.

def increment_helper(number):
    newNum = []
    if len(number) ==1:
        if number[0] == 1:
            carry = 1
            newNum.append(0)

        else:
            carry = 0
            newNum.append(1)
    else:
        return increment_helper(number-1)
    return newNum

So I'm sure that there are a lot of errors in here specifically how I am calling my recursion because I am not sure how to recurse on the list while storing the number that is removed somehow. The else return statement is obviously incorrect but I am using that as a placeholder. I am unsure of what condition to use as my base case for incrementation. I think I should be using a carry variable that keeps track of whether I am carrying a one over but other than that I am stuck on how to proceed.

Berezina

It looks like you want us to write some code for you. While many users are willing to produce code for a coder in distress, they usually only help when the poster has already tried to solve the problem on their own. A good way to demonstrate this effort is to include the code you've written so far, example input (if there is any), the expected output, and the output you actually get (console output, tracebacks, etc.). The more detail you provide, the more answers you are likely to receive. Check the FAQ and How to Ask. – Kroon

Recursive, binary number in list form, no conversion. Wow, that's a lot of constraints. Can we assume this is a homework assignment? – Originally

Your last sentence boils down to writing the entire function. Please read and follow the posting guidelines in the help documentation. On topic and how to ask apply here. StackOverflow is not a design, coding, research, or tutorial service. – Filmer

Sorry I'm really new to stack overflow. How do I add code that is formatted? – Berezina

Edit your original question. Paste the code where you want it. Then select the entire block and click on the "code" icon, which is a pair of braces { }. If you can't find it on your screen, just add your code, and one of us will do the formatting clicks. – Filmer

How do I format my post with Markdown or HTML in the Help center. Also, various "help" and "?" as well as a preview while you are editing. Strangely you didn't have this problem with your last question. – Demmy

Is "recursion" part of the set rules here? Makes not much sense ... – Enlist

It's an algorithmic problem that specifies that recursion must be used. The iterable solution is super easy to me and makes sense, but this problem is conditional on recursion. – Berezina

Answer 1

Ah, ha! Okay, you have some idea of what you're doing. The basic outline is

Base case: how do I know when I'm done?

You're done when you run out of digits. number should be a list of individual digits; check its length to figure out when not to recur.

Recursion case: what next?

The general concept of recursion is "do something simple, reduce the problem by a small amount, and recur with the smaller problem." Your job in this part is to do the addition for one digit. If you need to keep going (is there a carry from that digit?), then recur. Otherwise, you have all the info you need to finish.

Specific application

Your recursion step will involve calling increment_helper with one digit less: not number - 1, but number[:-1].

After you return from each recursion, you'lll then want to append the digit you just finished. For instance, if you're incrementing 1101, your first call will see that the right-hand one, incremented, has a carry. The new digit is 0, and you have to recur. Hold onto the 0 for a moment, call yourself with 110, and get the result of that call. Append your saved 0 to that, and return to your main program.

Does that get you moving?

Filmer

Answer 2

This one is "tricky" because you have two things going at each step:

1. what is the current number I'm looking at? (binary question 0/1)
2. should it be incremented? (do we have carry?) (binary question yes/no)

This leads to 4 cases.

There is the extra "case" of did we even get a list but it isn't that interesting.

So I would describe it as follows:

if not carry:
    # technically meaningless so just return the entire list immediately
    return list

# we have "carry", things will change
if not list:
    # assumes [] == [0]
    return [1]

if list[0]:
    # step on `1` (make it 0 and carry)
    return [0] + increment(rest_of_list)

# step on `0` (make it 1 and no more carry)
return [1] + rest_of_list

I strongly advise to change lists to tuples and work with these.

Also note that the recursion is on the reversed list, so apply as follows:

def increment_helper(lst, carry):
    if not carry:
        return lst

    if not lst:
        return [1]

    if lst[0]:
        return [0] + increment_helper(lst[1:], True)

    return [1] + lst[1:]


def increment(lst):
    # long but really just reverse input and output
    return increment_helper(lst[::-1], True)[::-1]

I used some shortcuts by returning lists immediately (short-circuiting), but you can make it more "pure" by carrying on the recursion even without carry.

Sigmon

Answer 3

You can treat the (binary) digits recursively by traversing the number from tail to head (just like addition works).

Before performing the recursion you have to check for two special cases:

• No increment at the current digit is to be performed. Then just return the unmodified digits.
• A single digit remains (you're at the head of the number). Then you possibly need to append the overflow to the head.

For the remaining cases you can increment the current digit and treat all digits before the current one in a recursive manner.

def bin_incr(n, incr=True):
    if not incr:
        return n
    if len(n) == 1:
        return [1, 0] if n[0] == 1 else [1]
    return (
        # `n[-1] == 1` denotes an overflow to the next digit.
        bin_incr(n[:-1], n[-1] == 1)
        + [(n[-1] + 1) % 2]
    )

Aviv

in this solution do you need to change the value of the incr variable to 0 if n[0] != 1 when checking for len(n) == 1 condition? – Berezina

@Sean In the len(n) == 1 condition there is no need to modify incr because you will return a fixed size list: [1, 0] in case there is an overflow and [1] otherwise (since an increment must have happened). – Aviv

I like your solution a lot for its elegance, and I understand most of it. What I don't understand yet is what the n[-1] == 1 stands for. Is that a pythonic way of saying if the last element in the list is one and if so how does that relate to the section in the function call incr=1. Sorry if I'm being slow about this. Recursion is the one concept that really messes with my head sometimes. – Berezina

@Sean Yeah good point, as I actually mixed two different types here. So incr should simply denote whether to increment or not (so it's actually a boolean variable, however for the sake of brevity I've set it to 1; we're always incrementing by 1 anyway). The n[-1] == 1 part simply denotes whether there is an overflow to the next digit, evaluating to True if that's the case. So for each recursive call the value of incr is actually True or False based on whether there is an overflow or not. I'll fix the answer for consistency. – Aviv

Ohhhhhh that makes so much more sense. I love your solution! I see that my problem was that I was thinking head first rather than tail first list traversal. That makes the problem trivial. Thank you so much for your help! – Berezina

Actually have you tested your solution? When I assert with: assert bin_incr([1,1,1]) = [1,0,0,0], "ERROR" , I am getting an error. – Berezina

@Sean Yes I did and I also don't get an error for your example. In your assertion you seem to have used a single = while comparing for equality should involve two ==. Is that a typo? Also what error do you get? What is the message? – Aviv

It is a typo. I think posting the code I have in the comments is too much. However, I even just straight copy pasted your code into atom and when I assert for converting [1,1,1] to [1,0,0,0] it does not function correctly. Maybe this is just something on my end that I need to figure out, but I'm surprised that it doesn't work even just straight up copy pasting. – Berezina

Nevermind. I figured out the issue. Thanks for your help. I really appreciate you taking the time to help me out. – Berezina

Answer 4

It may be best to use two functions: one to check if a simple increment of the last position would suffice and another to perform the recursion should the previous attempt fail:

vals = [[1, 0, 1], [1,1,1], [1,0,0,1]]
def update_full(d):
   if all(i in [1, 0] for i in d):
      return d
   start = [i for i, a in enumerate(d) if a > 1]
   return update_full([1]+[0 if i > 1 else i for i in d] if not start[0] else [a+1 if i == start[0] -1 else 0 if i == start[0] else a for i, a in enumerate(d)])

def increment(d):
    if not d[-1]:
       return d[:-1]+[1]
    return update_full(d[:-1]+[2])

print(list(map(increment, vals)))

Output:

[[1, 1, 0], [1, 0, 0, 0], [1, 0, 1, 0]]

Misplay

does d[-1] signify starting from the tail? – Berezina

@Sean The logic used my answer requires that the recursion starts from the tail, hence, d[-1]. – Misplay

Answer 5

Try this:

def add1(listNum):

    if listNum.count(0):
        oneArr = [[0] * (len(listNum) - 1)] + [1]
        sumArr = []
        for i in range(len(listNum)):
            sumArr.append(sum(listNum[i], oneArr[i]))
        newArr = []
        for j in range(len(sumArr) - 1):
            if sumArr[len(sumArr) - 1 - j] < 2:
                newArr.insert(0, sumArr[len(sumArr) - 1 - j])
            else:
                newArr.insert(0, 1)
                sumArr[len(sumArr) - 1 - j] += 1
        return sumArr

    else:
        return [1] + [[0] * len(listNum)]

There aren't many reasons for using recursion for a program as simple as this, which is why I have chosen to provide a non-recursive solution.

In case it interests you, I've calculated the time complexity of this function and it is O(n).

Cristie

I don't see the recursion step in this. Also, it seems overly complicated. – Filmer

Answer 6

Another recursive approach.

• Is the current input an empty list?

  • If yes return [1]
  • If no, continue

• Is the sum (value) of the last element in the list and 1 greater than 1?

  • If so recursively call your function on the list without the last element (number_list[:-1]) and append [0] to the result.
  • If no, set the last element of the list to the sum.

• Return the number_list

Code:

def increment_helper(number_list):
    if not number_list:
        return [1]

    value = number_list[-1] + 1

    if value > 1:
        number_list = increment_helper(number_list[:-1]) + [0]
    else:
        number_list[-1] = value

    return number_list

Example output:

numbers = [[1, 0, 1], [1,1,1], [1,0,0,1]]
for n in numbers:
    print("%r ---> %r" % (n, increment_helper(n)))
#[1, 0, 1] ---> [1, 1, 0]
#[1, 1, 1] ---> [1, 0, 0, 0]
#[1, 0, 0, 1] ---> [1, 0, 1, 0]

Collaboration

Answer 7

I understand you don't want to use decimal addition, but if you must use big endian bit order, converting back to decimal first is probably the most practical. Otherwise, you end up with unnecessary reverse calls or awkward negative array indices

def binary (dec): # big endian bit order
  if dec < 2:
    return [ dec ]
  else:
    return binary (dec >> 1) + [ dec & 1 ]

def decimal (bin, acc = 0):
  if not bin:
    return acc
  else:
    return decimal (bin[1:], (acc << 1) + bin[0])

def increment (bin):
  # sneaky cheat
  return binary (decimal (bin) + 1)

for x in range (10):
  print (x, binary (x), increment (binary (x)))

# 0 [0] [1]
# 1 [1] [1, 0]
# 2 [1, 0] [1, 1]
# 3 [1, 1] [1, 0, 0]
# 4 [1, 0, 0] [1, 0, 1]
# 5 [1, 0, 1] [1, 1, 0]
# 6 [1, 1, 0] [1, 1, 1]
# 7 [1, 1, 1] [1, 0, 0, 0]
# 8 [1, 0, 0, 0] [1, 0, 0, 1]
# 9 [1, 0, 0, 1] [1, 0, 1, 0]

If however you can represent your binary numbers in little endian bit order, things change. Instead of converting back to decimal, increment can be defined directly as a beautiful recursive function

def binary (dec): # little endian bit order
  if dec < 2:
    return [ dec ]
  else:
    return [ dec & 1 ] + binary (dec >> 1) 

def increment (bin):
  if not bin:
    return [1]
  elif bin[0] == 0:
    return [1] + bin[1:]
  else:
    return [0] + increment(bin[1:])

for x in range (10):
  print (x, binary (x), increment (binary (x)))

# 0 [0] [1]
# 1 [1] [0, 1]
# 2 [0, 1] [1, 1]
# 3 [1, 1] [0, 0, 1]
# 4 [0, 0, 1] [1, 0, 1]
# 5 [1, 0, 1] [0, 1, 1]
# 6 [0, 1, 1] [1, 1, 1]
# 7 [1, 1, 1] [0, 0, 0, 1]
# 8 [0, 0, 0, 1] [1, 0, 0, 1]
# 9 [1, 0, 0, 1] [0, 1, 0, 1]

Aside: converting the little endian representation back to decimal is a little different. I provide this to show that use cases for recursion exist everywhere

def decimal (bin, power = 0):
  if not bin:
    return 0
  else:
    return (bin[0] << power) + decimal (bin[1:], power + 1)

---

This part of the answer gives you cake and allows you to eat it too. You get big endian bit order and a recursive increment that steps through the bits in left-to-right order – You should use either implementation above for a number of reasons, but this aims to show you that even though your problem is complex, it's still possible to think about it recursively. No reverse or arr[::-1] was misused in the making of this function.

def binary (dec): # big endian bit order
  if dec < 2:
    return [ dec ]
  else:
    return binary (dec >> 1) + [ dec & 1 ]

def increment (bin, cont = lambda b, carry: [1] + b if carry else b):
  if bin == [0]:
    return cont ([1], 0)
  elif bin == [1]:
    return cont ([0], 1)
  else:
    n, *rest = bin
    return increment (rest, lambda b, carry:
                              cont ([n ^ carry] + b, n & carry))

for x in range (10):
  print (x, binary (x), increment (binary (x)))

# 0 [0] [1]
# 1 [1] [1, 0]
# 2 [1, 0] [1, 1]
# 3 [1, 1] [1, 0, 0]
# 4 [1, 0, 0] [1, 0, 1]
# 5 [1, 0, 1] [1, 1, 0]
# 6 [1, 1, 0] [1, 1, 1]
# 7 [1, 1, 1] [1, 0, 0, 0]
# 8 [1, 0, 0, 0] [1, 0, 0, 1]
# 9 [1, 0, 0, 1] [1, 0, 1, 0]

We start by breaking the problem up into smaller parts; n is the first problem, and rest is the rest of the problems. But the key to thinking with continuations (like cont above) is to think big.

In this particular problem, n gets updated based on whether rest gets updated. So we immediately recur on rest and pass a continuation that will receive the result of the subproblem. Our continuation receives the answer to the subproblem b, and whether or not that subproblem results in a carry.

...
  else:
    n, *rest = bin
    return increment (rest, lambda b, carry:
                              cont ([n ^ carry] + b, n & carry))

The n ^ carry and n & carry expressions determine what the answer to this subproblem is and what the next carry will be. The following truth table shows that ^ and & encodes our answer and next_carry respectively. For example, if n is 0 and carry is 1, the carry can be consumed. The answer will be [1] + the answer to the subproblem and the next carry will be 0.

n   carry   (answer, next_carry)   n ^ carry   n & carry
0   0       ([0] + b, 0)           0           0
0   1       ([1] + b, 0)           1           0
1   0       ([1] + b, 0)           1           0
1   1       ([0] + b, 1)           0           1

The base cases are simple. If the subproblem is [0], the answer is [1] and no carry of 0. If the subproblem is [1], then the answer is [0]with a carry of 1

...
  if bin == [0]:
    return cont ([1], 0)
  elif bin == [1]:
    return cont ([0], 1)

Lastly, design the default continuation – if the answer to the problem b results in a carry, simply prepend [1] to the answer, otherwise just return the answer.

cont = lambda b, carry: [1] + b if carry else b

Autonomic

Answer 8

You are asking for the increment/successor/next function that will generate a sequence of sequences. Since other have given code, I will give a general method for developing such functions.

First, develop a multiple recursion (2 or more recursive calls) for calculating, say, all sequences of the type of length N. For binary sequences (bs) in big-endian order, from N 0s to N 1s, the base case bs(0) expression is [[]], the sequence that contains the one sequence with no binary digits. The double recursion for bs(n) in terms of bs(n-1) is ([0] concatenated to all members of bs(n-1) (in order)) plus ([1] contanenated to all members of bs(n-1)).

Next, focus on the transition between the subsequences returned by adjacent recursive calls. Here there is just one: 0, 1, ..., 1 to 1, 0, ..., 0. To increment across this boundary, we need to replace 0 followed by 0 or more 1s by 1 followed by the same number of 0s. We find such breaks by scanning from the right for the first 0, as others have shown.

It turns out the every increment crosses the boundary between adjacent bs(k) calls for some value of k, which is to say, at some level of the tree of calls resulting from double recursion.

So far, that I know of, the same idea works for designing the increment function for sequences of grey codes, sequences of conbinations (n things taken k at a time), and sequences of permutations.

Note 1: the 1->0 transitions can be done 1 at a time or all at once.

Note 2: the binary bit testing and flipping is the turing machine algorithm for count + 1. Stephen Wolfram, A New Kind of Science, presents, as I remember, 3 different implementations in the TM chapter.

Note 3 (added in edit): If one switches from prepending 0 first to prepending 1 first, or from prepending to appending, or both, one gets 3 other sequence of sequences, with 3 other increment functions.

Shanty

Answer 9

You do not need recursion in this case. Let us start with the simplest implementation:

1. implement a full adder which will operate on bits.
2. implement a ripple adder using the full adder which will operate on 2 lists of bits.

The full adder implementation is straight forrward.

def full_adder(a,b,cin):
    sum_ = a^(b^cin)
    cout = (a&b) | (a|b)&cin
    return sum_, cout

Tests to make sure the full adder conforms to the specs:

>>> zero_one = (0,1)
>>> [full_adder(*x) for x in [(a,b,c) for a in zero_one for b in zero_one for c in zero_one]]
[(0, 0), (1, 0), (1, 0), (0, 1), (1, 0), (0, 1), (0, 1), (1, 1)]

Since the parameters of the ripple adder are lists, we need to ensure the list lengths match before the addition. This is done by padding the shorter list with leading zeros.

def ripple_adder(xs,ys):
    x, y = map(len, (xs, ys))
    alen = max(x, y)
    ax, by = map(lambda f: f if len(f) == alen else [0]*(alen-len(f)) + f, (xs, ys))
    cout = 0
    res = [0]*(alen)
    for i in range(alen-1, -1, -1):
        a, b, cin = ax[i], by[i], cout
        s, cout = full_adder(a, b, cin)
        res[i] = s
    if cout:
        res = [1] + res
    return res

Finally, we define bin_inc the binary increment function in terms of the ripple adder

def bin_inc(bin_lst):
    return ripple_adder(bin_lst, [1])

>>> bin_inc([1,1,1])
[1, 0, 0, 0]
>>> bin_inc([1,0,0,1])
[1, 0, 1, 0]

Now for a solution that is simpler but requires a little insight. Consider the following obervations for an input xs with length L and output ys

1. if xs is all ones, ys will have length L+1, the first element of ys will be 1 and the rest will be zeros.

2. if xs has a zero element, let p be the index of the last zero element in xs. Then ys will be the list consisting of the first p elements of xs followed by a 1 followed by zeros of length L - p. That is ys = xs[:p] + [1] + [0]*(L-p).

We can translate this to python code easily. We use python's list.index method to find the last occurence of zero by working on the reverse of the list and adjust the algorithm appropriately:

def bin_inc_2(xs):
    if all(xs):
        return [1] + [0]*len(xs)
    p = xs[::-1].index(0)
    return xs[:-p-1] + [1] + [0]*p

This works and is simpler than the ripple_adder based implementation. One minor drawback you might notice is when xs has a zero element, we traverse it to check if it is all ones, then traverse it again to find the first occurence of zero.

We can simplify the implementation and make it more pythonic atthe same time by using a try except block:

def bin_inc_3(bin_lst):
    try:
        p = bin_lst[::-1].index(0)
        return bin_lst[:-p-1] + [1] + [0]*p
    except ValueError: 
        return [1] + [0]*len(bin_lst)

This implementation is simple in terms of source text, and idiomatic python. Now we test it against the ripple_adder based adder to make sure it works well.

>>> z_n = (0,1)
>>> xs = [[a,b,c,d,e,f,g,h] for a in z_n for b in z_n for c in z_n for d in z_n
                            for e in z_n for f in z_n for g in z_n for h in z_n ]

>>> print(all(ripple_adder(x, [1]) == bin_inc_3(x) for x in xs))
True

Fantastic, it works as intended and correctly handles leading zeros as evidenced by the tests (which increments every number from 0 to 255).

Egan

Answer 10

There's only a need to recurse when there is a carry:

def f(n):
  # Base cases
  if not n:
    return [1]
  if n == [1]:
    return [1, 0]
  if n[-1] == 0:
    return n[:-1] + [1]
  if n[-2:] == [0, 1]:
    return n[:-2] + [1, 0]

  # Recurse
  return f(n[:-2]) + [0, 0]

numbers = [[1, 0, 1], [1,1,1], [1,0,0,1], [1, 0, 1, 1]]
for n in numbers:
  print n, f(n)

Spoilsport