FAQ: Recursion vs. Iteration - Coding Throwdown - Let's Give'em Sum Digits To Talk About

This community-built FAQ covers the “Let’s Give’em Sum Digits To Talk About” exercise from the lesson “Recursion vs. Iteration - Coding Throwdown”.

Paths and Courses
This exercise can be found in the following Codecademy content:

Learn Recursion: Python

FAQs on the exercise Let’s Give’em Sum Digits To Talk About

There are currently no frequently asked questions associated with this exercise – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this exercise. Ask or answer a question by clicking reply (reply) below.

If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this exercise, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.

Join the Discussion. Help a fellow learner on their journey.

Ask or answer a question about this exercise by clicking reply (reply) below!

Agree with a comment or answer? Like (like) to up-vote the contribution!

Need broader help or resources? Head here.

Looking for motivation to keep learning? Join our wider discussions.

Learn more about how to use this guide.

Found a bug? Report it!

Have a question about your account or billing? Reach out to our customer support team!

None of the above? Find out where to ask other questions here!

def sum_digits(n):
__sigma = 0
__x = str(n)
__for i in range(len(x)):
____sigma += int(x[i])
__return sigma

is my solution using iteration inefficient?
what is the O value of it?
[sorry for improper indentation it is my first question]

2 Likes

@etashtyagi7370687642, great question!

First, though, notice the </> icon at the center of the menu bar that appears when you begin to type. Use that, and you’ll save all your indentations, no need for th underscores.

The iterative solution offered involved popping off digits by alternating % and //
Yours involves converting the integer to a string, then summing the int() value of the character at each index.

Both methods are O(n) where n is the number of digits, as there is only one additional trip around the loop for each additional digit. (Since the number of digits increases as log(n), the time complexity would be O(log(N)) if N = the actual number whose digits are to be added, as opposed to the number of digits.)

But it is the nature of “big-O” that any algorithms with running time of O(n) may differ by a constant K*O(n), and still be considered to be in O(n).

So, I tested both methods using the very useful built-in Python timeit module, and the results showed pretty consistently that the “convert_str” method ran about 40 - 50% slower than the “div_mod” method.

Code here.
Results:

Total time for div_mod method, ten 12-digit numbers, 10000 runs each is 0.3153999000000002.
Total time for convert_str method, ten 12-digit numbers, 10000 runs each is 0.5629802999999997.
2 Likes

Simplified without recursion:

def sum_digits(n):
  return sum(int(number) for number in str(n))

Weird solution with recursion:

def sum_digits(n):
  return n if len(str(n)) == 1 else int(str(n)[-1]) + sum_digits(int(str(n)[:-1]))

Cleaner one:

def sum_digits(n):
  return n if not n else n % 10 + sum_digits(n // 10)

Can also be written like that:

def sum_digits(n):
  return n and n % 10 + sum_digits(n // 10)

Explanations: The first value in a and statement evaluated as False is returned, or the last one if all the value are True. It is different for a or statement which returns the first True value. It is not a proper way to do things althougth it is okay to use it while assigning variables.