【数据结构和算法思想】递归思想

递归的理解：

在程序中可以调用函数来完成任务，为了完成相同的任务可以调用同一个函数。如果在函数中调用函数本身，那么改函数就被称为递归函数。

递归代码模板：

void func() {
    // 递归结束条件：
    if(结束条件) {
        return;
    }

    // 函数执行逻辑
    // ......

    // 递归调用：
    func();
}

递归函数的调用是按层，不是次，有 N 层就同时调用（打开）了 N 个函数，不是 N 次。

无限递归（递而不归、死递归），栈溢出（函数的调用有时间和空间的开销，一个程序中同时调用的函数个数是有限的）。

递归函数分为两类：

• 在递去的过程中解决问题
• 在归来的过程中解决问题

举例说明：

• 递去过程中解决问题：前面人手中的子弹总数加上自己手上的，告诉下一个人，最后把子弹总数回传给上一个人。

• 归来的过程中解决问题：把消息传递下去，让最后的人把手中的子弹数告诉前一个人，前一个人加上后一个人告知的数量，继续向前传递。

递归函数的参数在每次调用时应该是不同的！

循环和递归：

• 递归函数的调用有时间和空间的开销，而且递归的次数受到堆栈大小的限制。
• 循环没有函数调用和返回中的参数传递和返回值的额外开销，更快。

如何在递归和循环之间选择？

一般情况下，当循环方法比较容易实现时，应该避免使用递归。当很难简历一个循环方法时，递归可能是一个很好的选择（某些情况下，递归方法总是显而易见的，而循环方法却是难以实现）

某些数据结构（树）本身就是递归时，则使用递归也是最好的方法了。

分而治之：

有一个问题A，把A分解成一系列比A更容易解决的子问题（A0，A1，A2 ...... ），如果解决所有的子问题（A0，A1，A2 ...... ），那么A问题也就解决了，这就是分而治之的思想。