Python | 一路递归深似海

本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。

问题描述

不知道小伙伴们在写代码时有没有遇到这种情况：每次写递归就莫名其妙地写出来了，没运行之前自己完全不知道对不对，就是写递归完全靠直觉。又或者一路递归深似海，从此回不来……，接下来让我们好好研究研究递归这个磨人的小妖精到底是怎样的。

解决方案

百度百科上对递归算法的定义如下：递归算法是指一种通过重复将问题分解为同类的子问题而解决问题的方法。相信很多小伙伴看了之后一脸懵逼，没关系，接下来我们用画图举例的方式来理解什么是递归。假如我们求一个列表 [1,3,5,7,9] 中所有数字的和，在不使用for和while的情况下来解决这个问题(为了方便举例给出的数据规模较小，实际上列表求和的数据是不确定有多少的)。我们认识到列表求和并不是把数据一块全加在一起一块算，它最终是由一次次的加法实现的，而加法恰有两个操作数，这个是确定的。因此我们可以把这个列表求和问题分解为规模更小且固定的两个数求和。为了实现问题规模的分解，我们换一个角度来看这个问题，将其写成下面这种表达式：(1+(3+(5+(7+9))))。对于这个式子，最内层的括号(7+9),这是无需循环就可以计算的，实际上整个求和过程如下：

观察上述过程的重复模式，列表求和实际上是这样的：列表的和 &