一、概念
1.递归
递归是指一个函数在其定义中直接或间接调用自身的编程方法 。简单来说，就是函数自己调用自己。递归主要用于将复杂的问题分解为较小的、相同类型的子问题，通过不断缩小问题的规模，直到遇到一个最简单、最基础的情况（基本情况），从而停止递归。
递归算法有两个过程，一是递推过程，二是回归的过程。
2.循环
循环是计算机科学运算领域的用语，也是一种常见的控制流程。循环是一段在程序中只出现一次，但可能会连续运行多次的代码。循环中的代码会运行特定的次数，或者是运行到特定条件成立时结束循环，或者是针对某一集合中的所有项目都运行一次。
二、执行过程
1.递归
在支持自调用的编程语言中，递归可以通过简单的函数调用来完成，如计算阶乘的程序在数学上可以定义为：
递归程序执行过程可分解为下图
2.循环
循环开始前需要初始化变量，然后进入表达式做判断，判断为true，执行循环体，判断为false则退出循环，输出结果
循环程序执行过程可分解为下图：
三、代码示例
1.go语言代码示例
package mainimport ("fmt""time"
)// 直接递归调用，求n的阶乘
// 参数:
//
// n - 一个正整数，表示需要计算阶乘的数字。
//
// 返回值:
//
// result - n 的阶乘结果。
func recursion(n int) (result int) {if n >= 1 {// 直接递归调用函数result = n * recursion(n-1)return result}return 1
}// loop 计算给定数字的阶乘。
// 参数:
//
// n - 一个正整数，表示需要计算阶乘的数字。
//
// 返回值:
//
// result - n 的阶乘结果。
func loop(n int) (result int) {// 当n < 0时，程序panic退出if n <= 0 {panic("Input must be a non-negative integer")}// 初始化 y 为 1，作为阶乘计算的起始值。y := 1// 从 1 循环到 n，逐步计算阶乘。for i := 1; i <= n; i++ {// 在每次循环中，将当前数字 i 与 y 相乘，累积阶乘结果。y *= i}// 返回计算得到的阶乘结果。return y
}func main() {// 初始化变量x为10，用于后续的递归和循环计算。x := 5// 开始递归计算，并记录开始时间。startRecurison := time.Now()// 打印递归计算的开始时间、结果以及花费的时间。fmt.Printf("recurison start time:%v, result:%d\n", startRecurison, recursion(x))fmt.Println("elapse time:", time.Since(startRecurison))// 开始循环计算，并记录开始时间。startLoop := time.Now()// 打印循环计算的开始时间、结果以及花费的时间。fmt.Printf("loop start time:%v, result:%d\n", startLoop, loop(x))fmt.Println("elapse time:", time.Since(startLoop))// 比较递归和循环的执行时间，判断哪个更快。if time.Since(startRecurison) > time.Since(startLoop) {fmt.Println("loop algorithm is faster")} else {fmt.Println("recursion algorithm is faster")}
}
2.查看执行结果
最终比较结果：循环算法的执行效率更好，速度更快
PS D:\Project\GoWorkSpace\DataStructure\0408> go run .\Recursion.go
recurison start time:2025-04-09 10:49:17.117547 +0800 CST m=+0.005692801, result:120
elapse time: 2.9766ms
loop start time:2025-04-09 10:49:17.1205236 +0800 CST m=+0.008669401, result:120
elapse time: 533.2µs
loop algorithm is faster
四、总结
1.递归和循环的区别
1.1内存占用
递归：每次调用都会在调用栈中保存当前状态，深度递归可能导致栈溢出（如 n=10000 时计算阶乘）。
循环：通常只占用常量内存（如几个变量）。
1.2效率
递归：函数调用需要额外开销（保存上下文、参数传递等），但某些语言支持尾递归优化（如 Scheme），可减少开销。
循环：通常更高效，无函数调用开销。
1.3可读性
递归：更符合分治、树遍历等问题的数学定义（如斐波那契数列、汉诺塔）。
循环：适合简单重复任务（如遍历数组）。
1.4典型场景
递归：分治算法（快速排序）、树/图遍历（DFS）、动态规划问题。
循环：线性操作（如求和、遍历）、需要严格控制资源时。
1.5转换与限制
- 相互转换
任何递归问题都可以用循环（+栈结构）实现，反之亦然，但代码复杂度可能变化。 - 限制
递归：受编程语言的调用栈深度限制。
循环：需手动管理状态，复杂逻辑可能使代码臃肿。
1.6总结表格
| 递归 | 循环 | |
|---|---|---|
| 实现方式 | 函数自我调用 | 显式迭代（for/while） |
| 内存占用 | 高（栈帧累积） | 低（常量空间） |
| 性能 | 可能因调用开销较慢 | 通常更高效 |
| 可读性 | 适合分治、树结构问题 | 简单直观 |
| 适用场景 | 分治、回溯、数学递归问题 | 线性操作、资源敏感任务 |
2.场景选择
用递归：问题本身是递归结构、代码简洁性优先（如树的遍历）
用循环：追求性能、处理大数据量、避免栈溢出风险。
概念补充
递归展开：指通过逐步展示递归函数的调用过程，将递归的每一层执行细节明确呈现出来，以直观理解递归如何分解问题、传递参数、返回结果。这一过程常用于分析递归逻辑、调试代码或手动模拟递归行为。
如果出现递归算法栈溢出，用循环算法优化也是一种方法
如有疏漏，欢迎评论区留言