了解递归堆栈 sum_integers

Question

我正在做一道关于递归的练习题。

实现sum_integers(n)，使用递归计算从1到所有整数的和。例如，sum_integers(3) 应该 return 6 ( 1+2+3 ).

我在没有真正理解我实际做了什么的情况下解决了这个问题...

def sum_integers(n):
    if n == 0:
        return 0
    else:
        return n + sum_integers(n-1)
    pass

基本情况，我明白了。

假设我们调用 sum_integers(3)

sum_integers(3)
  sum_integers(2)
      sum_integers(1)
         sum_integers(0)
            return 0

我不明白一旦我 return 0 what/how 它会返回堆栈。

在我的脑海里，这就是正在发生的事情

0 + sum_integers(1) = 0 + 1
0 + 1 + sum_integers(2) = 0 + 1 + 2
0 + 1 + 2 + sum_integers(3) = 0 + 1 + 2 + 3

虽然我不确定。我只是想更好地理解它。

Answer 1

0 + 1 + 2 + sum_integers(3) = 0 + 1 + 2 + 3 不是很正确，更简单的方法是

sum_integers(3)             # go down in recursion
3 + sum_integers(2)         # go down in recursion
3 + 2 + sum_integers(1)     # go down in recursion
3 + 2 + 1 + sum_integers(0) # go down in recursion
3 + 2 + 1 + 0               # stop because 'return 0'
3 + 2 + 1                   # go back and apply the plus
3 + 3                       # go back and apply the plus
6                           # go back and apply the plus

了解递归堆栈 sum_integers

understanding recursion stack sum_integers

python

recursion

stack

data-structures