如何更好地理解递归

1.前言

关于递归，其实网上有很多详细将这种思维的帖子，在代码里面最本质的体现就是函数自己调用自己，然后不停压栈（函数调用是压栈的一个过程，先进后出），直到遇到终止条件，再结果返回给上一层。但是我们在写代码的时候就容易陷入一个误区，一定要把程序完整的递归过程想出来后才开始写代码。你肯定就会有疑惑：把完整的递归过程想出来后，不是更应该方便我们写代码以及理解程序运行逻辑吗？但是，正如我前面所说，递归的本质就是函数调用自己（压栈），如果递归次数很多，你这时候思考的越多，你脑子就越容易 栈溢出 。

2.如何处理递归问题

处理递归，核心就是千万不要想子问题的过程，你脑子能处理几层？马上就绕迷糊了。要想子问题的结果，思路就清晰了。只要代码的边界条件和非边界条件的逻辑写对了 ，其他的事情交给数学归纳法就好了。也就是说，写对了这两个逻辑，你的代码自动就是正确的了，没必要想递归是怎么一层一层走的。这里的意思是直接假设子问题已经算出来了，不再思考子问题是怎么由子子问题计算的。

比如我们常见的斐波那契数列：f(n) = f(n-1) + f(n-2)，只要知道求解该数列第n个值的边界条件是n == 0和n == 1，然后根据这个数学表达式（非边界条件）就行，

int fibonacci(int n)
{
    if (n == 0 || n == 1) return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

3.总结

1. 如何思考二叉树相关问题？
   • 不要一开始就陷入细节，而是思考整棵树与其左右子树的关系。
2. 为什么需要使用递归？
   • 子问题和原问题是相似的，他们执行的代码也是相同的（类比循环），但是子问题需要把计算结果返回给上一级，这更适合用递归实现。
3. 为什么这样写就一定能算出正确答案？
   • 由于子问题的规模比原问题小，不断“递”下去，总会有个尽头，即递归的边界条件 ( base case )，直接返回它的答案“归”；
   • 类似于数学归纳法（多米诺骨牌），n=1时类似边界条件；n=m时类似往后任意一个节点
4. 计算机是怎么执行递归的？
   • 当程序执行“递”动作时，计算机使用栈保存这个发出“递”动作的对象，程序不断“递”，计算机不断压栈，直到边界时，程序发生“归”动作，正好将执行的答案“归”给栈顶元素，随后程序不断“归”，计算机不断出栈，直到返回原问题的答案，栈空。
5. 另一种递归思路
   • 维护全局变量，使用二叉树遍历函数，不断更新全局变量最大值。