Question

Use pseudocode to describe an algorithm for the procedure: int sum_digits( int number ). The procedure will recursively sum the individual digits in number. For example, when number=123, the procedure will return 6. State the time complexity of your solution and clearly identify your base case(s) and recursive case(s).

Answer 1

The program is written in python 3.x 

The time complexity of this program is O(n) where is the number of digits present in the number. This is because the recursion tree here is a linear tree with no branches (as we are only calling one recursion function at each step)so the height of the tree will be as same as the number of digits present in the number.


def sum_digits(number):
    # this is the base condition
    # this condition tells the program to stop when the number is a single digit number
    if(number<10):
        return number
    else:
        # this is the recursive step
        # Here we will take each and every single digit from the number and add it
        # the number%10 will give us the unit digit of the number 
        # the sum_digits(int(number/10)) will call the recursive function on number except the unit place and make the tens place as a new units place
        return (number%10) + sum_digits(int(number/10))

print(sum_digits(123456789))

def sum_digits(number): # this is the base condition # this condition tells the program to stop when the number is a single digit number if(number<10): return number else: # this is the recursive step # Here we will take each and every single digit from the number and add it # the number%10 will give us the unit digit of the number # the sum digits(int number/10)) will call the recursive function on number except the unit placeand tensplace as a new units place return (number%10) + sum_digits(int (number/10)) print(sum_digits(123456789)) samplex D:\Programming\pyhton \venv\Scripts\python.exe D:/Programming/pyhton/sample.py 45 Process finished with exit code o