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. 如何理解递归

递归是一种把问题分解成独立子问题来求解的编程方法，一个问题要使用递归来解决需要确定下面两个关键点：

1. 确定独立子问题的划分。

2. 确定递归的返回条件。

如果上面两点没有明确就开始撸代码，可能会导致无限递归下去，很容易把程序的栈给打爆。

下面通过一个简单的例子斐波那契数列带大家看一下递归的过程。

斐波那契数列的定义如下：

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)的结果在第一次计算完就保存下来，后面可以直接使用，提高程序的运行效率，这就是我们常说的空间换时间。这种实现方法也叫做备忘录法，刷题的时候是比较常见的。

上面的例子比较简单，目的是帮助大家更好理解递归，平时还需要多动手实践才能对递归有更深刻的理解。