递归

从程序上讲，调用自己。

递归代码

逆向思维

一个例子，计算 $ n! $，最基本的想法,思考方式，从 1 乘到 n。

$$n! = 1 \times 2 \times 3 \times \cdots \times n$$

int fun(int n)
{
    int result = 1;
    for (int i = 1;i <=n; i++)
        result = result * i;
    return result;
}

递归的思维方式：想计算 $ 4! $ ，如果已经计算好了 $ 3! $，那么在此基础上 $ \times 4 $ 就可以了。但是 $ 3! $ 的结果也不知道，那么如果知道 $ 2! $ 就好了，找到最后，$ 1! $ 是直接知道的，然后就可以一路找回去了。

#include <stdio.h>

int fun(int N)
{
    if (N == 1) return 1;
    return N * fun(N - 1);
}

int main()
{
    int n;
    while (scanf("%d", &n) != EOF)
        printf("%d\n", fun(n));
}

可以使用 echo 3 | ./a.out 或者直接写一个文本文件，然后 cat case | ./a.out 来做测试。

这段代码体现了递归的精髓。

int fun(void n)                 //递归函数定义
{
    if (n == 1) return 1;       // 基础情况处理，边界条件
        
    int temp = fun(n - 1);      //递归调用
    return temp*n;               //递推到当前层
}

函数定义明确这个函数做什么事情，

• 输入参数

• 做的事情：计算 $ n! $ 并返回

基础情况阶段，要考虑当期那规模足够小、答案显而易见的时候写死答案并直接返回。这也是递归停止的条件。

递归调用阶段，每次让数据规模(或问题规模)减小一点，并调用递归函数以获得较小规模的答案。

递推阶段，将上一层答案进行简单递推，得到上一层答案。

举例，斐波那些数列

数学上的递归是容易理解的，$ f(0) = 0, f(1) = 1, f(n) = f(n-1) + f(n-2) $

思维：从最终的答案出发找上一层的答案，然后构造当前层的答案。

#include <stdio.h>

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

int main()
{
    int n;
    while (scanf("%d", &n) != EOF)
        for (int i=0; i<=n; i++)
            printf("%d ", fun(i));
        printf("\n");
}

同样的使用 echo 6 | ./a.out 来输出

经典的汉诺塔问题(比较复杂的递归)

leetcode 上一个汉诺塔题目

#define MAX_NUMS 15

struct column{
    int * disc;
    int nums;
    char name;
};

typedef struct column * column_t;

void hanoi(int n, column_t from, column_t to, column_t via)     //递归要解决的问题
{
    if (n == 1)                                                 //最简单的情况的处理
    {
        to->disc[to->nums] = from->disc[from->nums - 1];
        to->nums++;
        from->nums--; 
        printf("%c -> %c\n", from->name, to->name);
        return;
    }
    hanoi(n - 1, from, via, to);                                //递归调用，递推到当前层
    hanoi(1, from, to, via);
    hanoi(n - 1, via, to, from);
}

void hanota(int* A, int ASize, int* B, int BSize, int** C, int* CSize){
    column_t a = malloc(sizeof(struct column));
    column_t b = malloc(sizeof(struct column));
    column_t c = malloc(sizeof(struct column));

    a->disc = A;
    a->nums = ASize;
    a->name = 'a';

    b->disc = malloc(MAX_NUMS * sizeof(int));;
    b->nums = 0;
    b->name = 'b';

    c->disc = malloc(MAX_NUMS * sizeof(int));;
    c->nums = 0;
    c->name = 'c';

    hanoi(a->nums, a, c, b);

    *C = c->disc;
    *CSize = c->nums;
}

如何理解递归

参考 https://www.zhihu.com/question/443721615/answer/1954217542

理解递归前，要理解 return 的含义，三层含义：

• 1.返回值是什么

• 2.返回到什么什么位置

• 3.返回到上一级(上一层)

递归也是一种循环，和 while 循环一样，会执行相同的代码。如果一个问题在执行过程中可以拆出一个形式完全一样的子问题，那可以用递归解决。而且递归都有可以直接解决的边界情况，一旦边界条件解决了，那么大规模的问题也就可以逐步解决。

递归的条件：

• 问题可以分解为多个重复的子问题（子问题仅存在数据规模的差距，比如　f(2) 和 f(1)。

• 存在终止条件。

编写递归的代码，要考虑清楚两个问题：找出重复的子问题（递推公式） + 终止条件。

涉及到递归问题，不要想太多，就是找出它的递推公式和终止条件。

递归时会遇到的问题：

栈溢出，程序报错，直接终止，一般是代码上的问题。

重复计算，这是性能上的问题，优化的方式：判重+记录结果