Creating a recursive function that removes odd digits of an integer

Question

I just started working with recursive functions and I have to create a function that receives an integer and returns a new number that contains only the even digits. For example if it receives 23456, it should return 246. This is what I've tried:

def newInt(n):
    dig = n % 10
    if dig % 2 == 1:
        return newInt(n//10)
    elif dig % 2 == 0:
        return str(n) + newInt(n//10)

print(newInt(32))

But I'm getting the following error:

RecursionError: maximum recursion depth exceeded in __instancecheck__

Any hints on what should I do to fix it?

fwiw, recursion specifically in Python (but not necessarily in other languages!) is usually the wrong solution.. curiosity is always welcome, however! — ti7, May 26 '22 at 01:35
Where would the recursion stop? You currently have no stop mechanism... hint, if n is 0 you can stop. — Julien, May 26 '22 at 01:35
@ti7 I'm learning this method on an online course, so I'm trying different exercises — theJohnLewis, May 26 '22 at 01:37
Does this answer your question? [Why is Python recursion so expensive and what can we do about it?](https://stackoverflow.com/questions/67988828/why-is-python-recursion-so-expensive-and-what-can-we-do-about-it) — ti7, May 26 '22 at 01:38
Yup, that fixed the error, now I have to check why it's duplicating the number instead of doing what it's supposed to do — theJohnLewis, May 26 '22 at 01:42
@ti7 this is not really relevant. Sure there is a point where it is important to understand when to use recursion or not. But before that you need to just learn how to do recursion, which is where OP is at now. — Julien, May 26 '22 at 01:43
@theJohnLewis the reason it's duplicating the number is that you have `return str(n) + newInt(n//10)` which should be `return str(dig) + newInt(n//10)` — Nick, May 26 '22 at 01:44
I see, I just corrected that. Recursion is being more confusing than I thought, thanks a lot! — theJohnLewis, May 26 '22 at 01:45
Also it should be `return newInt(n//10) + str(dig)` otherwise the digits come out in the wrong order — Nick, May 26 '22 at 01:46
@Julien why not to do something can be equally as relevant as how it can be done, and both should be brought and cause for excitement! just imagine how much time would be wasted if students went away from their classes without knowing linked lists manufacture cache misses! — ti7, May 26 '22 at 01:48

score 1 · Answer 1 · answered May 26 '22 at 01:41

You need a base case. There's also no need to convert any of the integers to strings. Here is a working version of newInt() that resolves both of these issues:

def newInt(n):
    if not n:
        return 0
    dig = n % 10
    if dig % 2 == 1:
        return newInt(n // 10)
    else:
        return 10 * newInt(n // 10) + dig

score 0 · Accepted Answer · answered May 26 '22 at 01:41

Your issue is that you have no condition to stop recursion - every call to newInt results in another call. One way to stop would be to check if n is less than 10 and then just return n if it is even. For example:

def newInt(n):
    if n < 10:
        return n if n % 2 == 0 else 0
    dig = n % 10
    if dig % 2 == 1:
        return newInt(n//10)
    elif dig % 2 == 0:
        return newInt(n//10) * 10 + dig

Note I have modified your function to return an integer rather than a string.

mozway · Answer 3 · 2022-05-26T01:53:52.920

0

Here is a variant with divmod. Uncomment the print to see how it works:

def newInt(n):
    d,r = divmod(n,10)
    # print(n,d,r)
    if d == 0:
        return 0 if r%2 else r
    if r % 2:
        return newInt(d)
    else:
        return 10*newInt(d)+r
    
print(newInt(212033450))

Output: 22040

edited May 26 '22 at 01:53

answered May 26 '22 at 01:51

mozway

194,879
13
39
75

Mulan · Answer 4 · 2022-05-26T03:33:21.257

This is a rewrite of @mozway's algortihm using Python 3.10 match..case syntax -

def newInt(n):
  match divmod(n, 10):
    case (0, r) if r & 1:
      return 0
    case (0, r):
      return r
    case (d, r) if r & 1:
      return newInt(d)
    case (d, r):
      return 10 * newInt(d) + r

print(newInt(67120593306737201))

Note r & 1 is more efficient for testing if a number is even or odd. r % 2 performs division whereas & simply checks the first bit.

score 0 · Answer 5 · answered May 26 '22 at 03:32

0

You don't even need to break out dig for each loop:

def newInt(n):
    if n:
        if n & 1:
            return newInt(n // 10)
        else:
            return 10 * newInt(n // 10) + (n % 10)
    return 0

answered May 26 '22 at 03:32

RufusVS

4,008
3
29
40

Creating a recursive function that removes odd digits of an integer

5 Answers5