Day 8 - Pre-Knowledge for Recursion
Day8 - 递归前置知识
1. 递归的介绍
递归是一种解决问题的方法，它把一个问题分解成一个或多个独立的子问题。
所有递归函数都包含两部分:
定义一个(或多个)基本情况，也就是递归的出口，它决定了递归什么时候停止，否则递归将永远继续下去，直到程序的栈被打爆!
将问题分解为更小的独立子问题并递归调用，即递归关系。
最常见的递归例子是斐波那契数列。
递归出口：
fib(0) = 0和fib(1) = 1递归关系：
fib(i) = fib(i - 1) + fib(i - 2)
int fib(int n) {
if (n <= 1) {
return n;
}
return fib(n - 1) + fib(n - 2);
}面试中涉及到递归的有二分查找、归并排序、树的遍历、深度优先搜索等
2. 注意的事情
一定不要忘记定义递归的出口条件。明确基本用例的数量，在上面的斐波那契数列示例中，注意我们的一个递归调用调用
。这表明你应该定义两个基本用例（
和 
的情况），以便你的代码涵盖输入范围内所有可能的函数调用。如果递归函数只调用
，那么只需要定义一个基本用例。排列问题，树相关的问题在面试中经常出现，你要知道如何使用递归来生成一个序列的全排列，以及如何去重，还要熟练掌握树的各种遍历的递归实现。
递归隐式地使用栈来实现。因此，所有递归方法都可以使用迭代的方法利用栈进行重写。需要注意递归级别太深而导致栈溢出(Python的默认限制是1000)。递归的实现一般不会有
的空间复杂度，因为涉及到栈，除非有尾部调用优化(TCO)。不同的语言对尾部调用优化支持的情况也是不一样的。
3. 边界的条件
实际上也就是上面提到的递归出口。
Fib中需要提前定义
n=0、n=1的情况确保有足够的基本用例来覆盖所有可能的递归函数调用
4. 优化的方法
在某些情况下，可能需要计算先前计算过的结果。让我们再看一下斐波那契的例子。fib(5)调用fib(4)和fib(3)， fib(4)调用fib(3)和fib(2)。其中fib(3)被调用了两次，如果记住fib(3)的值并再次使用，则大大提高了算法的效率，时间复杂度变为O(n)，这就是常用的备忘录法，在刷题中经常会遇到。
可以额外占用一点空间复杂度，存下已经计算过的值，可以极大提高递归的时间效率！
5. 如何理解递归
递归是一种把问题分解成独立子问题来求解的编程方法，一个问题要使用递归来解决需要确定下面两个关键点：
确定独立子问题的划分。
确定递归的返回条件。
如果上面两点没有明确就开始撸代码，可能会导致无限递归下去，很容易把程序的栈给打爆。
下面通过一个简单的例子斐波那契数列带大家看一下递归的过程。
斐波那契数列的定义如下：
fib(0) = 0
fib(1) = 1
fib(n) = fib(n - 1) + fib(n - 2), n >= 2求解fib(4)的c++代码如下，为了更容易理解，我在函数的入口，出口以及递归返回的条件都加了打印。
#include <iostream>
#include <iomanip>
int fib(int n) {
std::cout << std::setw((4-n)*4)<< " " << "开始计算fib(" << n <<")\n" << std::endl;
if (n == 0) {
std::cout<< std::setw((4-n)*4) << " " << "n == 0,返回0\n" << std::endl;
return 0;
}
if (n == 1) {
std::cout<< std::setw((4-n)*4) << " " << "n == 1,返回1\n" << std::endl;
return 1;
}
int res = fib(n - 1) + fib(n - 2);
std::cout << std::setw((4-n)*4)<< " " << "计算fib(" << n <<")结束\n" << std::endl;
return res;
}
int main()
{
int n = 4;
int res = fib(n);
std::cout << " f(" << n << ") = " << res << "\n" << std::endl;
return 0;
}编译运行，输出如下：
开始计算fib(4)
开始计算fib(3)
开始计算fib(2)
开始计算fib(1)
n == 1,返回1
开始计算fib(0)
n == 0,返回0
计算fib(2)结束
开始计算fib(1)
n == 1,返回1
计算fib(3)结束
开始计算fib(2)
开始计算fib(1)
n == 1,返回1
开始计算fib(0)
n == 0,返回0
计算fib(2)结束
计算fib(4)结束
f(4) = 3整个运行过程相当于对下面这棵树进行深度优先搜索。
用gdb对编译出来的二进制进行调试，在返回条件if (n == 1)代码分支中加入断点，运行二进制，等程序断下来后，执行命令bt查看函数调用栈。
GDB是Linux下非常好用且强大的调试工具。GDB可以调试C、C++、Go、Java、 Objective-c、PHP等语言。对于以后想称为一个Linux下工作的c/c++程序员，GDB是必不可少的工具，所以本篇来从零讲解GDB在LInux的调试。
对于GDB调试器来说，不像VS编译器中那样的图形化界面形式，而是采用纯命令行的形式进行调试。So 在开始学习的时候，大家可能会感觉晦涩难懂，但是这是C/C++程序员必须要掌握的技能
(gdb) bt
#0 fib (n=1) at test.cpp:12
#1 0x0000000000400a2b in fib (n=2) at test.cpp:16
#2 0x0000000000400a2b in fib (n=3) at test.cpp:16
#3 0x0000000000400a2b in fib (n=4) at test.cpp:16
#4 0x0000000000400ac4 in main () at test.cpp:24可以看出来函数的调用顺序和我们上面日志中输出的顺序是一致的。
我们常说递归是通过栈来实现的，就是因为递归中会用到栈来保存函数的调用顺序。
上面对斐波那契数列的递归实现不是最优的，通过打印我们可以看到fib(2)被计算了多次，其实可以将fib(2)的结果在第一次计算完就保存下来，后面可以直接使用，提高程序的运行效率，这就是我们常说的空间换时间。这种实现方法也叫做备忘录法，刷题的时候是比较常见的。
上面的例子比较简单，目的是帮助大家更好理解递归，平时还需要多动手实践才能对递归有更深刻的理解。
Last updated