需要递归方面的帮助

Question

我正在尝试使用递归计算数组中 5 个数字的总和。但是，我从递归函数得到的输出为 0。如果我取消注释 print 语句，我得到的总和为 15，但该函数返回的总和为 0。我在这里做错了什么？我的代码-def calcsum(arr):  i = 0  sum = 0  solution(arr,sum,i)  return sumdef solution(arr,sum,i):  if i == len(arr):    return  sum = sum + arr[i]  #print(sum,i)  solution(arr,sum,i+1)print(calcsum([1,2,3,4,5]))

Answer 1

您的代码至少存在五个问题：

• solution(arr, sum, i)对in的调用calcsum不会修改calcsum局部变量sum，因此calcsum始终返回 0；

• 您在 中 中编写了return而不是return sum在最终情况下进行递归solution，因此在这种情况下solution将返回None而不是返回总和

• 您将递归调用编写为solution(arr,sum,i+1)而不是return solution(arr,sum,i+1)or some_variable = solution(arr,sum,i+1)，因此无论如何都会忽略递归调用的返回值；return除了块内的语句之外，没有任何语句if，因此该函数solution不会有返回值（或者更准确地说，它将返回None）；

• 您似乎相信修改sum内部solution会修改sum整个程序中调用的任何变量。这是错误的。sum是函数的局部变量，修改它对程序的其余部分没有影响。

• 在 python 中调用变量sum是一个坏主意；这是内置函数的名称，因此您应该尝试为变量找到另一个名称。

为了说明第四点，请尝试以下代码：

def mostly_harmless(n):

  n = 7

n = 8

mostly_harmless(n)

print('Does this set n to 7? Am I about to print 8 or 7?')

print(n)

print()

mostly_harmless(12)

print('did we set 12 = 7? did we just break all of mathematics?')

print('making sure 12 is still 12:')

print(12)

print('making sure n is still n:')

print(n)

考虑到这一点，我们可以修复您的代码：

def calcsum(arr):

  return solution(arr, 0, 0)

def solution(arr, sum, i):

  if i == len(arr):

    return sum

  else:

    return solution(arr, sum + arr[i], i+1)

print(calcsum([1,2,3,4,5]))

实际上，我们可以使用默认参数进一步简化代码：

def calcsum(arr, sum=0, i=0):

  if i == len(arr):

    return sum

  else:

    return calcsum(arr, sum + arr[i], i+1)

print(calcsum([1,2,3,4,5]))

但请注意，python并不是一门喜欢递归的语言。在其他一些编程语言中，递归非常好，并且与 for 循环和 while 循环一样高效。但在 python 中却并非如此。在Python中，递归比循环慢得多，并且使用更多的内存。我们可以用 for 循环重写你的程序：

def calcsum(arr):

  sum = 0

  for i in range(len(arr)):

    sum += arr[i]

  return sum

print(calcsum([1,2,3,4,5]))

或者甚至更好：

def calcsum(arr):

  sum = 0

  for v in arr:

    sum += v

  return sum

print(calcsum([1,2,3,4,5]))

另请注意，在 python 中调用变量sum是一个坏主意，因为sum是 python 中内置函数的名称。您可以在python 文档中找到内置函数列表；尝试为您的变量指定其他名称。

毫不奇怪，该函数sum自行计算总和：

print(sum([1,2,3,4,5]))

那么为什么调用变量这么糟糕呢sum？好吧，那么我们就失去了对同名内置函数的访问：

sum = 7

print(sum([1,2,3,4,5]))

# Traceback (most recent call last):

#   File "<stdin>", line 1, in <module>

# TypeError: 'int' object is not callable

通常sum指内置函数；但现在它引用一个等于7;的变量 当我尝试调用 时sum([1,2,3,4,5])，就好像我尝试调用一样7([1,2,3,4,5])，这是没有意义的，因为它7不是一个函数。

Answer 2

您可以使其按您的方式工作，即增加sum中的变量calcsum，如果您将solution其放入其中并增加外部sum而不是拥有自己的变量。arr那么也无需通过。

def calcsum(arr):

  def solution(i):

    nonlocal sum

    if i == len(arr):

      return

    sum = sum + arr[i]

    solution(i+1)

  sum = 0

  solution(0)

  return sum

print(calcsum([1,2,3,4,5]))

Answer 3

正如已经提到的，您应该返回总和。这是一个迭代器版本：

def calcsum(arr):

    return solution(iter(arr), 0)

def solution(it, sum):

    for x in it:

        return solution(it, sum + x)

    return sum

print(calcsum([1,2,3,4,5]))

仅使用一个函数和一个参数的更短方法，在递归x 后添加：

def calcsum(it):

    it = iter(it)

    for x in it:

        return x + calcsum(it)

    return 0

print(calcsum([1,2,3,4,5]))

两种解决方案都需要线性时间，而类似的解决方案只需要arr并将其分成arr[0]和arr[1:]，而后者需要整体二次时间。通过对 1000 个值的列表求和来比较此迭代器版本与该列表版本的一个小基准测试：

0.28 ms  calcsum_1

2.70 ms  calcsum_2

基准代码：

from timeit import repeat

def calcsum_1(it):

    it = iter(it)

    for x in it:

        return x + calcsum_1(it)

    return 0

def calcsum_2(arr):

    if arr:

        x, rest = arr[0], arr[1:]

        return x + calcsum_2(rest)

    return 0

arr = [1] * 1000

for _ in range(3):

    for f in calcsum_1, calcsum_2:

        t = min(repeat(lambda: f(arr), number=1000))

        print('%.2f ms ' % t, f.__name__)

    print()

Answer 4

请记住，递归至少有两种情况：

• 基本情况：返回合计值

• 递归情况：返回递归结果

这两种情况都不会返回值！试试这个：

def solution(arr, sum_, i):

    if i == len(arr):

        return sum_

    sum_ += arr[i]

    return solution(arr, sum_, i+1)

此外，仅仅调用solution不会改变sumin的值calcsum，因此return sum总是给出0. 尝试改为：

def calcsum(arr):

    return solution(arr, 0, 0)

（顺便说一句，这种创建函数的结构，将调用委托给带有一些附加参数的助手，这让我想起了很多 Haskell，你可以在其中编写：

calcsum :: Num a => [a] -> a

calcsum = go 0 0

  where go :: Num a => Int -> Int -> [a] -> a

        go acc idx xs

            | length xs >= idx = acc

            | otherwise        = go (acc + (xs !! idx)) idx+1 xs

另外你的逻辑有点复杂。考虑一下类似的事情：

def solution(arr):

    if arr:

        # Recursive case

        x, rest = arr[0], arr[1:]

        return x + solution(rest)

    else:

        # Base case

        return 0

现在的基本情况是当arr为空时（而不是当您传递了数组外部的索引时）。您计算空列表的总和，该列表只能在逻辑上通过0。递归情况将第一个元素从列表中拉出，并将其添加到列表其余部分的解决方案中。