Understanding Recursion Using Sum of Digits
Explore how to apply recursion to solve the sum of digits problem in Python. Understand the process of breaking down problems into smaller cases, identifying base conditions, and tracing the call stack. Learn why recursion simplifies code and fits naturally with self-similar problems, enhancing your problem-solving skills.
Previous lessons introduced recursion, explained how the call stack works, and outlined when to use recursion instead of iteration. This lesson applies those concepts in practice. It uses a classic introductory problem, the sum of digits, to reinforce recursive problem-solving techniques.
The problem
Given a number, find the sum of all its digits. For example:
sumOfDigits(123)→1 + 2 + 3 = 6sumOfDigits(456)→4 + 5 + 6 = 15sumOfDigits(9)→9
Simple enough to understand, but how do we solve it recursively?
Thinking recursively
Before writing any code, let’s think about the problem the way a recursive function would.
The key question to ask is: can I solve a smaller version of this problem and use that answer to solve the full problem?
Look at the number 123. Its last digit is 3 ...