Recursion - SyntaxError: invalid syntax

Question

I am trying to write a recursive method as follows, but I am getting SyntaxError: invalid syntax, I wonder what I am doing wrong

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

class Solution(object):
    def addDigits(self, num):
        """
        :type num: int
        :rtype: int
        """
        return self.addDigits(x=sum(i for i in str(num)) if x%9<10:

Note: I am learning recursion in python, therefore rather than knowing how to solve problem, I would love to learn what I am doing wrong in my implementation.

So what's the code supposed to do when x >= 10? If you want help fixing code, you have to explain what the code is supposed to do. — Aran-Fey
– Aran-Fey, Commented Apr 23, 2018 at 15:01
what are you passing to num as? it looks like maybe a string and you want to add the digits? — Grant Williams
– Grant Williams, Commented Apr 23, 2018 at 15:01
Yeah, that is invalid syntax, and I can't even guess what it's supposed to do… — deceze
– deceze ♦, Commented Apr 23, 2018 at 15:02

Grant Williams · Accepted Answer · 2018-04-23 16:00:23Z

2

Updated to match the new question description:

def add_digits(x):
    return (x - 1) % 9 + 1 if x else 0

If you apply the brute force version of this solution (the one you were originally attempting) then you will see the output is actually the sequence listed here: https://oeis.org/A010888.

Once we know that this is a repeating sequence we can look for patterns in the sequence, and in this case we realize that the function in this answer provides a guaranteed solution in O(1) time and space.

You can actually see the relationship to n % 9 by seeing this sequence here: https://oeis.org/A010878

edited Apr 23, 2018 at 16:00

answered Apr 23, 2018 at 15:05

Grant Williams

1,5471 gold badge12 silver badges24 bronze badges

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

7 Comments

casillas Over a year ago

I am learning recursion method, therefore rather than knowing how to solve problem, I would love to learn what I am doing wrong in my implementation. I have upvoted your effort.

Mihai Chelaru Over a year ago

@GrantWilliams your answer only adds the digits up, but does not produce the desired single digit outcome the OP was asking for (i.e. returns 11 for 38 instead of 2)

Grant Williams Over a year ago

@MihaiChelaru You are correct. When i originally wrote the answer, the question was quite a bit more ambiguous

Grant Williams Over a year ago

@hotspring you actually don't need recursion (or iteration) to solve this problem. If you are just learning about recursion i'd really recommend looking into something like the Fibonacci sequence or a factorial program. It's a lot easier to wrap your head around.

Grant Williams Over a year ago

The sequence is called the additive digital root of n seq 888. You can read more about it if you like, or you can see that the sequence of n % 9 i.e. seq 878 (ignoring the base case of 0) is the same except that seq878 is 0-8 instead of 1-9 like seq888 is. We can use this new sequence, seq878, and adjust our current value to fit it by subtracting 1 from x and then doing modulo 9 (making it part of seq878 then adding 1 back to it to convert back to seq888.

|

Collectives™ on Stack Overflow

Recursion - SyntaxError: invalid syntax

1 Answer 1

7 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Related