递归方法的理解

递归思想算是编程中比较常见但对初学者而言又有些难以理解的方法了。在leetcode上刷了几道题都用递归思想成功解决后觉得应该贯彻互联网的开源共享精神，总结一下自己的爬坑经历了

记得在第一次碰见递归是在学C语言的时候，当时讲解递归这种编程思想用了一个例子：求n!

由于C语言很久不用代码格式已经忘记=_=！因此这里用python重写一遍这个函数：

def f(n):
    if n == 1:
        return 1
    return n * f(n-1)

不得不说这是一个非常简单的例子来讲解递归函数：一个函数在内部调用其自身。这种调用很很巧妙得避免了利用for循环来求解n的阶乘这个问题因此让当时身为初学者的我也能感受到递归函数的强大。

但这个例子看起来容易，但递归实际操作起来却有一定难度。尤其是让自己写一个稍微复杂点的递归时，发现自己逻辑就混乱不清。自己其实也经历过这样一个过程，开始的时候死活无法理解，后来网上搜了搜如何理解递归。在知乎看到两种解释自己十分受用，自己现在能成功解决一个递归问题也是得益于这两种思想：

1.递归其实与数学归纳法有类似之处。数学归纳法是怎么处理问题的呢？首先我们证明在初始情况（一般也是n=1）是成立的，然后假设当n=k时成立，由n=k成立推导出n=k+1时成立。这个过程应该是感到非常熟悉，操作起来也是犹如行云流水了。那么递归呢？非常类似，首先我们要列出相对于数学归纳法里初始情况(n=1)时函数的返回值，这相当于递归函数碰到的特殊情况（求n!时，当n=1可以看做是一种特殊情况）。列出特殊情况后，在写出普遍情况下函数如何执行（也就是n != 1时的情况），这时我们就要推导n = k和n=k-1的关系了，因为我们在执行n=k时需要用到n=k-1时的结果。这时又要用到第二个思想。

2.在写一个递归函数时，可以将递归函数看做一个黑匣子（黑匣子就是我们不管也不知道其中细节，也不理解是怎么实现的，总之就是能实现功能的）。它可以接收一个输入并给出想要的输出，注意，此时要有自信，相信自己写的这个函数可以完成预期的功能。如果这么想，当把n=k-1输入这个函数时，输出的自然就是当n=k-1时我们想要得到的输出，此时我们要相信这个输出是已经解决了n=k-1这种情况的。那么省下的步骤就是在n=k是调用n=k-1时函数输出的结果了，也就是上一个思想中的推导n=k时的输出对n=k-1时的输出的依赖关系了。

上面两种思想：一种是将递归看成数学归纳法的实现过程，另一种是将递归看成一个黑匣子。如果是完成一个递归思想编程任务应该可以完成了。但是这样还是不够的：我们不能总是面对一个自己写的黑匣子吧？

如何搞清楚这个黑匣子的内部结构呢？

建议自己对着一个比较复杂的递归函数（自己当时是花了一个下午的时间看着leetcode上Binary Watch的递归解决方法来理解的），一步一步不嫌麻烦得画出这个函数是如何实现自我调用的，也就是将函数自我调用的栈画出来。就会探知黑匣子内部其实是一环扣一环的关系，就像数学归纳法由一步推出下一步。自己实现一到两次就会对消除的黑匣子的恐惧。

最后自己按照上面的两个思想实现一个递归函数，自己实现了一次后有了信心后面再碰到就得心应手了，理解起来也更加轻松。

：）最后祝大家爬坑愉快