How to change this function to recursive

Question

I have a function find_numbers() which returns all n-digit numbers whose sum of digits is divisible by 2.

For example, find_numbers(2) will return: [11, 13, 15, 17, 19, 20, 22, 24, 26, 28, 31, 33, 35, 37, 39, 40, 42, 44, 46, 48, 51, 53, 55, 57, 59, 60, 62, 64, 66, 68, 71, 73, 75, 77, 79, 80, 82, 84, 86, 88, 91, 93, 95, 97, 99]

Question: How can I change find_numbers() to be recursive? (in python)

def find_numbers(n: int):
   result = []

   for i in range(10**(n - 1), 10**n):
      if (sum_of_digits(i) % 2 == 0):
         result.append(i)

   return result

# helper function to sum all digits of a number
def sum_of_digits(n: int) -> int:
   result = 0
   for digit in str(n):
      result += int(digit)
   return result

I've just created this recursive version, but it doesn't work. I don't know what is wrong in the following code:

def find_numbers(n: int):
   def find_numbers_helper(n: int, i: int):
      if (i < 10 ** n):
         if (sum_of_digits(i) % 2 == 0):
            return [i].append(find_numbers_helper(n, i + 1))            

   return find_numbers_helper(n, i=10 **(n-1))

For information, your second function is sum(map(int, str(n))). — Guimoute
– Guimoute, Commented Jan 18, 2021 at 19:37
The sum of a number's digits = the first digit + the sum of the rest of the digits. — General Grievance
– General Grievance, Commented Jan 18, 2021 at 19:38
and this is a one liner: find_numbers = lambda n:[i for i in range(10**(n - 1), 10**n) if sum(map(int, list(str(i)))) % 2 == 0] — armamut
– armamut, Commented Jan 18, 2021 at 19:41
ok yes maybe it can be solved in one line but I really want to see a solution as a recursive version of find_numbers. I have more complex task to do and I just simplified it to simplier problem only to ask for your help. — Maad Maad
– Maad Maad, Commented Jan 18, 2021 at 19:45

Alain T. · Accepted Answer · 2021-01-20 16:27:05Z

Recursivity often requires approaching the problem differently. Most notably as a refinement of a simpler solution. For example, by adding digits to numbers of the larger N-size making the total even only on the last digit. You can keep track of the even/odd state of the sum of digits as you add them at each recursion level.

Here is an example as a recursive generator:

def evenDigits(N,prefix=0,odd=0):
    if N == 1: # only add odd or even digits at last position
        yield from (prefix*10+d for d in range(odd,10,2))
        return
    for d in range(prefix==0,10): # start at 1 when prefix is zero
        yield from evenDigits(N-1,prefix*10+d,(odd+d)%2)

output:

for n in evenDigits(3): print(n)
101
103
105
107
109
110
112
114
116
118
121
123
...
987
989
990
992
994
996
998

This is much different from an iterative approach where you would typically just filter numbers on the sum of their digits:

def evenDigits(N):
    yield from (n for n in range(10**(N-1),10**N) if sum(map(int,str(n)))%2==0)

Maad Maad · Accepted Answer · 2021-01-18 21:03:57Z

0

I have a solution!

def find_numbers(n: int) -> list:
   def find_numbers_helper(result: list, n: int, i: int):
      if (i < 10 ** n):
         if (sum_of_digits(i) % 2 == 0):
            result.append(i)
         
         find_numbers_helper(result, n, i + 1)

   result = list()
   find_numbers_helper(result, n, i=10 **(n-1))

   return result

Can it be improved (not by removing recursion)?

answered Jan 18, 2021 at 21:03

Maad Maad

931 silver badge8 bronze badges

Comments

Kien Nguyen · Accepted Answer · 2021-01-19 05:56:48Z

Problem in your solution

The first time you call find_numbers_helper(), the value of i will be 10^x, so sum_of_digits(i) will be 1 and sum_of_digits(i)% 2 == 0 is always False. Hence the statement return [i].append(find_numbers_helper(n, i + 1)) is unreachable. As a result, find_numbers_helper() is called only once and returns nothing.
The second problem is that your solution is essentially an iterative approach (loop through all the numbers less than 10^n and check the sum of their digits). To write a recursively function, you need to have a recursive approach that I will give the example below.

My solution

The idea of this solution is to choose each digit from left to right, each time we choose 1 digit and recursively call to choose the next digit. At each step we store current number num and remainder of "sum of the digits" divided by 2. Recursion ends when we choose the last digit (choose even digit if the remainder is even and odd digit in the opposite case).

Below is an example code:

def find_numbers(n: int, num = 0, remainder = 0):
    if n == 1:
        return [num * 10 + digit for digit in range (remainder, 10, 2)]
    result = []
    for digit in range (num == 0, 10):
        result += find_numbers(n - 1, num * 10 + digit, (remainder + digit) % 2)
    return result

print(find_numbers(1))
# [0, 2, 4, 6, 8]
print(find_numbers(2))
# [11, 13, 15, 17, 19, 20, 22, 24, 26, 28, 31, 33, 35, 37, 39, 40, 42, 44, 46, 48, 51, 53, 55, 57, 59, 60, 62, 64, 66, 68, 71, 73, 75, 77, 79, 80, 82, 84, 86, 88, 91, 93, 95, 97, 99]

Collectives™ on Stack Overflow

How to change this function to recursive

3 Answers 3

Comments

Comments

Problem in your solution

My solution

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Problem in your solution

My solution

Comments

Your Answer

Sign up or log in

Post as a guest

Related