递归算法分析

Question

我试图找出这个算法，它接受int的输入，并且应该返回int中每个元素之和的输出。

# Input -> 4321
# output -> 10 (4+3+2+1) 

def sum_func(n):

    # Base case
    if len(str(n)) == 1:
        return n

    # Recursion
    else:
        return n%10 + sum_func(n/10)

当我试图分解这个算法时，这就是我想出来的

1st loop -> 1 + 432 = 433
2nd loop -> 2 + 43 = 45
3rd loop -> 3 + 4 = 7
4th loop -> 4 + 4 = 8

它是如何得出10的结果的？

Answer 1

松开时，它会是这样的：

sum_func(4321)
= 1 + sum_func(432)
= 1 + 2 + sum_func(43)
= 1 + 2 + 3 + sum_func(4)
= 1 + 2 + 3 + 4

Answer 2

当试图理解递归时，您必须清楚地了解返回的内容。

在本例中，函数sum_func(n)在其参数n中返回数字的和。

具体的n任务分为last_digit_of_n + sum_func(n_without_last_digit)。

例如,

sum_func(4321) = sum_func(432) + 1 = sum_func(43) + 2 + 1 = sum_func(4) + 3 + 2 + 1 = 4 + 3 + 2 + 1

希望这能有所帮助。

(顺便指出，使用str检查n是否有多个数字是个坏主意。最好只是检查一下n <= 9)

Answer 3

在进行求和之前，必须到达基本情况：

Iteration 1: 1 + sum_func(432)
Iteration 2: 1 + 2 + sum_func(43)
Iteration 3: 1 + 2 + 3 + sum_func(4) = 1 + 2 + 3 + 4 = 10