Recursive function for divisibility test of 11?

user_13353851 0
Viewed 1858

The divisibility test for 11 states if the difference between the sum of odd digits and the sum of even digits in a number is divisible by 11, the entire number is said to be divisible by 11.

For example, 7689, whereby the sum of odd digits = 9 + 6 = 15, while sum of even digits = 8 + 7 = 15.

As (15 - 15) % 11 == 0, the number is divisible by 11.

I wrote an iterative function to evaluate this, giving a result of True if the number is indeed divisible by 11. How do I write a recursive version of this code? I have trouble breaking down this problem.

def divisible_by_11_iter(num):
    num_lst = [i for i in str(num)]
    even_sum = 0
    odd_sum = 0
    for even in num_lst[::2]: # naming does not really matter as negatives taken into acc
        even_sum += int(even)
    for odd in num_lst[1::2]:
        odd_sum += int(odd)
    if (odd_sum - even_sum) % 11 == 0:
        return True
    else:
        return False
recursion python
2 Answers

Your current code isn't iterative, it just "cheats" by doing an actual modulus of the difference at the end. If you can do something % 11 == 0, you should do that to num at the top and not mess around with summing digits at all.

Anyway, to implement this recursively, you need to figure out what the base cases are that you can trivially solve. I suggest that you can solve positive values less than 11 pretty trivially. Zero is divisible, all the numbers between 0 and 11 are not divisible.

For larger numbers, you do the digit summing and recurse.

def divisible_by_11(num):
    if num == 0:
        return True
    if num < 11:
        return False
    num_lst = [int(i) for i in str(num)]
    even_sum = sum(num_lst[::2])
    odd_sum = sum(num_lst[1::2])
    return divisible_by_11(abs(even_sum - odd_sum))
user_14050650 
def rec(num, oddsum=0, evensum=0, odd=True):
    m = num % 10 # First we extract the mod 10 and thus, effectively remove the first digit
    num = num // 10

    if odd:
        oddsum += m
    else:
        evensum += m

    if num == 0:
        return abs(oddsum - evensum) % 11 == 0 # Finally to end the recursion
    return rec(num, oddsum, evensum, not odd) # Notice how we flip the odd variable. So it becomes even in the next call.


print(rec(7689))
print(rec(11))
print(rec(22))
print(rec(420))

#Output

True
True
True
False
user_54046940
Related