递归算法分析：整数各位数字求和算法执行结果疑问

Hey there! Let's break down where your reasoning went wrong, and show how the correct output of 10 is actually calculated.

First, The Code Bug #

First off, your original code has a critical issue in the recursive step: using n/10 instead of integer division n//10. In Python 3, / returns a float (e.g., 4321/10 = 432.1), which will mess up both the len(str(n)) check and the subsequent calculations. We'll use // for the correct execution walkthrough.

Why Your Step-by-Step Was Incorrect #

You've got the order of recursion backwards! Recursion works by first drilling down to the base case before any addition happens. Your steps assumed immediate addition at each call, but the actual execution waits until the base case is hit, then sums values on the way back up.

Correct Execution Walkthrough (With Fixed Code) #

Here's what happens when we run sum_func(4321) with n//10 instead of n/10:

1. First call: sum_func(4321)

   • len(str(4321)) is 4 (not 1), so we calculate: 4321 % 10 + sum_func(4321//10) → 1 + sum_func(432)
   • We don't add 1 and 432 yet—we first need to resolve sum_func(432)

2. Second call: sum_func(432)

   • len(str(432)) is 3 (not 1), so: 432 %10 + sum_func(432//10) → 2 + sum_func(43)
   • Again, we wait to resolve sum_func(43)

3. Third call: sum_func(43)

   • len(str(43)) is 2 (not 1), so: 43%10 + sum_func(43//10) → 3 + sum_func(4)
   • Wait to resolve sum_func(4)

4. Fourth call: sum_func(4)

   • len(str(4)) is 1—this triggers the base case! We return 4 directly.

Now we start backtracking and adding:

• sum_func(43) becomes 3 + 4 = 7
• sum_func(432) becomes 2 +7 =9
• sum_func(4321) becomes 1 +9 =10

That's where the correct output of 10 comes from!

Fixing Your Original Code #

Just replace / with // in the recursive step, and it'll work as intended:

def sum_func(n):
    # Base case
    if len(str(n)) == 1:
        return n
    # Recursion with integer division
    else:
        return n %10 + sum_func(n//10)

内容的提问来源于stack exchange，提问作者edmamerto