Python递归函数如何在tri_recursion函数中工作？

Question

我是 Python 的新手，我发现 下面的递归程序 很难理解。在调试程序时，我发现它通过递归并且每次递归时 k 的值会减少 1。在某个点上，k 变成了 -1，编译器就会转到 else 部分并返回 0。

最后，k 的值变成了 1，这是怎么发生的呢？

def tri_recursion(k):
  if(k>0):
    result = k+tri_recursion(k-1)
    print(result)
  else:
    result = 0
  return result

print("\n\nRecursion Example Results")
tri_recursion(6)

和输出：

Recursion Example Results  
1  
3  
6  
10  
15  
21  

- Balaji

---

使用这个可视化工具：http://pythontutor.com/visualize.html#code=def%20tri_recursion%28k%29%3A%0A%20%20if%28k%3E0%29%3A%0A%20%20%20%20result%20%3D%20k%2Btri_recursion%28k-1%29%0A%20%20%20%20print%28result%29%0A%20%20else%3A%0A%20%20%20%20result%20%3D%200%0A%20%20return%20result%0A%0Aprint%28%22%5Cn%5CnRecursion%20Example%20Results%22%29%0Atri_recursion%286%29&cumulative=false&curInstr=0&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false。它将帮助您了解递归如何使用堆栈概念工作。 - Pygirl

请查看以下链接以更好地理解：http://cryptroix.com/2016/10/10/understanding-multiple-recursion/ - Pygirl

我认为这个链接很好地展示了发生的事情。 - carlot0820

Answer 1

尝试使用纸和笔追踪该函数。在这种情况下，函数内的打印语句可能会有点误导性。

考虑程序的这一部分，

if(k>0):
    result = k+tri_recursion(k-1)
...

从这里开始，

tri_recursion(6) = 6 + tri_recursion(5)

因此，要得到tri_recursion(6)的结果，我们必须先得到tri_recursion(5)的结果。按照这个逻辑，问题就简化为：

tri_recursion(6) 
 = 6 + tri_recursion(5) 
 = 6 + 5 + tri_recursion(4)
 = 6 + 5 + 4 + tri_recursion(3)
 = 6 + 5 + 4 + 3 + tri_recursion(2)
 = 6 + 5 + 4 + 3 + 2 + tri_recursion(1)
 = 6 + 5 + 4 + 3 + 2 + 1 + tri_recursion(0)

现在请注意，0不大于0，因此程序转到else子句的主体部分：

else:
    result = 0
...

这意味着 tri_recursion(0) = 0。因此：

tri_recursion(6) 
= 6 + 5 + 4 + 3 + 2 + 1 + tri_recursion(0)
= 6 + 5 + 4 + 3 + 2 + 1 + 0
= 21

注意事项

1. 在运行该程序时，k永远不会等于-1，实际上这是不可能的。
2. 将控制流程视为“编译器在程序中移动”是误导性的。编译器在执行期间并不做任何事情（JIT是另一回事）。更好的方法是从过程式语言的控制流/执行顺序、函数式编程的方程式和逻辑编程的关系角度来思考。

- Xero Smith

Answer 2

如果你像这样调试代码

def tri_recursion(k):
    if(k > 0):
        print('\t'*k,'start loop k',k)
        holder = tri_recursion(k - 1)
        result = k + holder
        print('\t'*k,'i am k(', k,')+previous result(', holder,')=',result)
    else:
        result = 0
        print('i reached when k =', k)
    print('\t'*k,'end loop', k)
    return result

print("\n\nRecursion Example Results")
tri_recursion(6)

你会看到类似下面的输出

Recursion Example Results
                         start loop k 6
                     start loop k 5
                 start loop k 4
             start loop k 3
         start loop k 2
     start loop k 1
i reached when k = 0
 end loop 0
     i am k( 1 )+previous result( 0 )= 1
     end loop 1
         i am k( 2 )+previous result( 1 )= 3
         end loop 2
             i am k( 3 )+previous result( 3 )= 6
             end loop 3
                 i am k( 4 )+previous result( 6 )= 10
                 end loop 4
                     i am k( 5 )+previous result( 10 )= 15
                     end loop 5
                         i am k( 6 )+previous result( 15 )= 21
                         end loop 6
21

- Datalicious