Understanding Recursion Using Sum of Digits
Explore how to use recursion to solve the sum of digits problem in Python. Learn to identify base and recursive cases, trace the call stack, and understand why recursion simplifies problems with self-similar structures.
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 ...