# 递归算法
递归（Recursion）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法，其核心思想是分治策略。
## :pencil2: 递归和迭代
**递归**（recursion）：递归常被用来描述以自相似方法重复事物的过程，在数学和计算机科学中，指的是在函数定义中使用函数自身的方法。（A调用A）
**迭代**（iteration）：重复反馈过程的活动，每一次迭代的结果会作为下一次迭代的初始值。迭代使用循环实现的，也可以看作一种循环。（A重复调用B）
递归三要素：
1. 明确函数功能**，**先不管函数里面的代码逻辑是什么，首先要明确自己定义的函数用来干什么。
2. 寻找递归出口，不然就会出现死循环，最终导致栈溢出`StackOveflowError`。
3. 寻找函数的等价关系式，不断的缩小参数范围。
迭代三要素：（循环三要素：循环变量、循环体和循环终止条件）
1. 有一个有初始值的变量。
2. 一个说明变量值怎么更新的规则。
3. 一个结束条件。
递归是一个**树结构**，从字面可以其理解为重复 “递推” 和 “回归” 的过程，当 “递推” 到达底部时就会开始 “回归”，其过程相当于树的深度优先遍历。（***线性递归和树形递归***）
迭代是一个**环结构**，从初始状态开始，每次迭代都遍历这个环，并更新状态，多次迭代直到到达结束状态。（***线性迭代和环形迭代***）
理论上递归和迭代时间复杂度方面是一样的，但实际应用中（函数调用和函数调用堆栈的开销）递归比迭代效率要低。\
### :pen\_fountain: 区别与联系
相同点：
* 都是通过控制一个变量的边界（或者多个），来改变多个变量为了得到所需要的值，而反复而执行的；
* 都是按照预先设计好的推断实现某一个值求取（请注意，在这里循环要更注重过程，而递归偏结果一点）。
不同点：
递归通常是逆向思维居多，“递” 和 “归” 不一定容易发现；而循环从开始条件到结束条件，包括中间循环变量，都需要表达出来。
递归算法与迭代算法的设计思路区别在于：函数或算法是否具备收敛性，当且仅当一个算法存在预期的收敛效果时，采用递归算法才是可行的，否则，就不能使用递归算法。简单的来说就是：**用循环能实现的，递归一般可以实现，但是能用递归实现的，循环不一定能实现，往往需要借助一个栈，因为递归调用就是在内存中进行函数压栈的过程。**
### :pen\_fountain: **递归转迭代**
递归转迭代
理论上递归和迭代可以相互转换，但实际从算法结构来说，递归声明的结构并不总能转换为迭代结构。**即迭代可以转换为递归，但递归不一定能转换为迭代（往往代价很高）。**
将递归算法转换为非递归算法有两种方法，一种是直接求值（迭代），不需要回溯；另一种是不能直接求值，需要回溯。前者使用一些变量保存中间结果，称为直接转换法，后者使用栈保存中间结果，称为间接转换法。
**直接转换法**
直接转换法通常用来消除**尾递归**（tail recursion）和**单向递归**，将递归结构用迭代结构来替代。（单向递归 → 尾递归 → 迭代）
**间接转换法**
递归实际上利用了系统堆栈实现自身调用，我们通过使用栈保存中间结果模拟递归过程，将其转为非递归形式。
尾递归函数递归调用返回时正好是函数的结尾，因此递归调用时就不需要保留当前栈帧，可以直接将当前栈帧覆盖掉。
## :pencil2: **题型**
### :pen\_fountain: **1、反转链表**
链表是一种兼具递归和迭代性质的数据结构。反转链表的问题具有递归性质，即子问题和原问题的结构完全相同。
#### [reverse-linked-list](https://leetcode-cn.com/problems/reverse-linked-list/)
#### [reverse-linked-list-ii](https://leetcode-cn.com/problems/reverse-linked-list-ii/)
#### [**Reverse Nodes in k-Group**](https://leetcode-cn.com/problems/reverse-nodes-in-k-group/)
#### [swap-nodes-in-pairs](https://leetcode-cn.com/problems/swap-nodes-in-pairs/)
> 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。 **不能只是单纯的改变节点内部的值**，而是需要实际的进行节点交换。
### :pen\_fountain: 2、二叉树遍历
二叉树也是一种兼具递归和迭代性质的数据结构。二叉树的相关算法基本都可以同时用递归和迭代实现。
```cpp
/* 二叉树遍历框架 */
void traverse(TreeNode root) {
// 前序遍历
traverse(root.left)
// 中序遍历
traverse(root.right)
// 后序遍历
}
```
### :pen\_fountain: 3、快排 & **归并**排序
对比模板可以看出：**快速排序就是个二叉树的前序遍历，归并排序就是个二叉树的后续遍历。**
{% tabs %}
{% tab title="快速排序" %}
```cpp
void sort(int[] nums, int lo, int hi) {
/****** 前序遍历位置 ******/
// 通过交换元素构建分界点 p
int p = partition(nums, lo, hi);
/************************/
sort(nums, lo, p - 1);
sort(nums, p + 1, hi);
}
```
{% endtab %}
{% endtabs %}
{% tabs %}
{% tab title="归并排序" %}
```cpp
void sort(int[] nums, int lo, int hi) {
int mid = (lo + hi) / 2;
sort(nums, lo, mid);
sort(nums, mid + 1, hi);
/****** 后序遍历位置 ******/
// 合并两个排好序的子数组
merge(nums, lo, mid, hi);
/************************/
}
```
{% endtab %}
{% endtabs %}
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://mqjyl2012.gitbook.io/algorithm/algorithm/recursive-algorithm.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.