为什么要用递归

编程里面估计最让人摸不着头脑的基本算法就是递归了。很多时候我们看明白一个复杂的递归都有点费时间，尤其对模型所描述的问题概念不清的时候，想要自己设计一个递归那么就更是有难度了。

很多不理解递归的人，总认为递归完全没必要，用循环就可以实现，其实这是一种很肤浅的理解。因为递归之所以在程序中能风靡并不是因为他的循环，大家都知道递归分两步，递和归，那么可以知道递归对于空间性能来说，简直就是造孽，这对于追求时空完美的人来说，简直无法接接受，如果递归仅仅是循环，估计现在我们就看不到递归了。

递归之所以现在还存在是因为递归可以产生无限循环体，也就是说有可能产生100层也可能10000层for循环。例如对于一个字符串进行全排列，字符串长度不定，那么如果你用循环来实现，你会发现你根本写不出来，这个时候就要调用递归，而且在递归模型里面还可以使用分支递归，例如for循环与递归嵌套，或者这节枚举几个递归步进表达式，每一个形成一个递归。

用归纳法来理解递归

数学都不差的我们，第一反应就是递归在数学上的模型是什么。毕竟我们对于问题进行数学建模比起代码建模拿手多了。

（当然如果对于问题很清楚的人也可以直接建立递归模型了，运用数模做中介的是针对对于那些问题还不是很清楚的人）

自己观察递归，我们会发现，递归的数学模型其实就是归纳法，这个在高中的数列里面是最常用的了。回忆一下归纳法。

归纳法适用于想解决一个问题转化为解决他的子问题，而他的子问题又变成子问题的子问题，而且我们发现这些问题其实都是一个模型，也就是说存在相同的逻辑归纳处理项。当然有一个是例外的，也就是递归结束的哪一个处理方法不适用于我们的归纳处理项，当然也不能适用，否则我们就无穷递归了。这里又引出了一个归纳终结点以及直接求解的表达式。如果运用列表来形容归纳法就是：

步进表达式：问题蜕变成子问题的表达式
结束条件：什么时候可以不再是用步进表达式
直接求解表达式：在结束条件下能够直接计算返回值的表达式
逻辑归纳项：适用于一切非适用于结束条件的子问题的处理，当然上面的步进表达式其实就是包含在这里面了。

这样其实就结束了，递归也就出来了。递归算法的一般形式：

void func( mode)
{
    if(endCondition)
    {
        constExpression         //基本项
    }
    else
    {
        accumrateExpreesion     //归纳项
        mode=expression         //步进表达式
            func(mode)          //调用本身，递归
    }
}

最典型的就是N!算法，这个最具有说服力。理解了递归的思想以及使用场景，基本就能自己设计了，当然要想和其他算法结合起来使用，还需要不断实践与总结了。

#include "stdio.h"
#include "math.h"

int main(void)
{
    int n, rs;

    printf("请输入需要计算阶乘的数n：");
    scanf("%d",&n);

    rs = factorial(n);
    printf("%d ", rs);
}

// 递归计算过程
int factorial(n){
     if(n == 1) {
          return 1;
     }
     return n * factorial(n-1);
}

对于递归，最好的理解方式便是从函数的功能意义的层面来理解。

了解一个问题如何被分解为它的子问题，这样对于递归函数代码也就理解了。

这里有一个误区（我也曾深陷其中），就是通过分析堆栈，分析一个一个函数的调用过程、输出结果来分析递归的算法。这是十分要不得的，这样只会把自己弄晕，其实递归本质上也是函数的调用，调用的函数是自己或者不是自己其实没什么区别。在函数调用时总会把一些临时信息保存到堆栈，堆栈只是为了函数能正确的返回，仅此而已。我们只要知道递归会导致大量的函数调用，大量的堆栈操作就可以了。

小结

递归的基本思想是把规模大的问题转化为规模小的相似的子问题来解决。

在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一个方法，所以就产生了函数调用它自身的情况。

另外这个解决问题的函数必须有明显的结束条件，这样就不会产生无限递归的情况了。

chat

详细介绍一下递归

递归（Recursion）是一种在函数内部调用自己的编程技术，它常用于解决可以被分解成子问题、且子问题结构与原问题相同的问题。

一、递归的基本结构

递归函数通常包含两个核心部分：

终止条件（Base Case） 告诉函数何时停止递归。如果没有终止条件，递归会无限进行下去，导致程序崩溃（比如栈溢出）。
递归调用（Recursive Case） 把原问题分解成一个或多个更小的子问题，并调用自己来解决这些子问题。

示例：阶乘（Factorial）

public int factorial(int n) {
    if (n == 0 || n == 1) {
        return 1;  // 终止条件
    }
    return n * factorial(n - 1);  // 递归调用
}

二、递归的执行过程

以 factorial(3) 为例，执行过程如下：

factorial(3)
= 3 * factorial(2)
= 3 * (2 * factorial(1))
= 3 * (2 * 1)
= 6

每次调用都会被压入调用栈，直到遇到终止条件，再一层层返回。

三、递归的应用场景

递归特别适合处理结构重复或者问题可以拆分成子问题的场景：

应用类型	示例说明
数学问题	阶乘、斐波那契数列
数据结构遍历	树的遍历（前序、中序、后序）、图遍历
分治算法	归并排序、快速排序
回溯问题	全排列、八皇后问题、数独
动态规划（带记忆）	斐波那契优化版、最小路径和等
DFS 深度搜索	图搜索、迷宫路径、连通块统计等

四、递归与迭代的比较

对比项	递归	迭代
思维模式	更抽象，更贴近数学建模	更贴近底层实现
性能	消耗较大（调用栈、函数开销）	更快，占用内存少
代码风格	简洁、可读性好	相对冗长，但性能好
可替代性	一般都可以转成迭代	反之不一定（如回溯）

五、常见陷阱

没有终止条件，或终止条件不正确

// 错误示例：没有终止条件
public void infinite() {
    infinite();  // 死循环
}

重复计算：性能低下 如斐波那契数列的递归版会重复计算很多相同的值
```
public int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2); // 大量重复调用
}
```
✅ 改进：使用记忆化缓存（Memoization）

六、递归优化技巧

技术	说明
记忆化搜索（缓存）	减少重复计算，提高效率
尾递归优化	某些语言（如Scala）支持尾递归优化
改为迭代实现	用栈手动管理调用过程，提升效率

七、Java 递归注意事项

Java 没有自动尾递归优化。
递归层数过多（如上万）时，可能会栈溢出（StackOverflowError）。
使用 Map、数组、Set 等结构辅助缓存中间结果可以优化性能。

八、总结口诀：递归三问

我能把问题分解成更小的吗？
最小的情况（终止条件）是什么？
每一步递归是否都向终止条件靠近？

参考资料

为什么要用递归
用归纳法来理解递归
小结
chat
详细介绍一下递归
参考资料

leetcode recursive 递归-01-递归基本概念介绍