首先，理解递归。众所周知，人脑的栈是有限且远远达不到计算机的水平的，所以，要想在大脑中或者通过纸笔一层层的模拟理解递归，最终的结果只有一个，就是把自己绕在里面。理解递归的第一步，就是要纵观全局。
理解递归
理解递归最好的方案就是二叉树的遍历，要完成一棵二叉树的遍历，最简单的实现莫过于递归的方式了，以力扣144题：二叉树的前序遍历为例，一份可行的递归代码实现如下所示：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
#define MAX_NODE_NUN 100
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
int *ret = malloc(sizeof(int) * (MAX_NODE_NUN+1));
*returnSize = 0;
preorder(root, returnSize, ret);
return ret;
}
void preorder(struct TreeNode* root, int* retIndex, int *ret) {
if (root == NULL) {
return;
}
ret[(*retIndex)++] = root->val;
preorder(root->left, retIndex, ret);
preorder(root->right, retIndex, ret);
}
在核心的 preorder() 函数中，只做了三件事情：
- 边界/终止条件控制：当节点为空时，直接返回
- 做操作，此例中为将节点的值加入数组末尾
- 分别遍历左子树
root->left和右子树root->right，也就是递归的部分
而这三步，基本上是所有递归程序的通用步骤，你如果需要探求实际的执行过程，你只需要保证解决问题的方法无误，边界控制无误，那么最终结果就会是正确的。（当然，初学时可以使用比较小型的二叉树画着理解下执行过程，以及将递归的过程转使用循环的代码写出来
理解回溯
所谓回溯，其实就是多次执行递归，以你题目中的问题为例，结合你的图分析你的代码：
void backTracking(int* nums, int numsSize, int* used) {
if(pathTop == numsSize) {
copy();
return;
}
int i;
for(i = 0; i < numsSize; i++) {
if(used[i])
continue;
used[i] = 1;
path[pathTop++] = nums[i];
backTracking(nums, numsSize, used);
//回溯
pathTop--;
used[i] = 0;
}
}-
if判断的作用： 终止条件控制 -
for循环的作用：依次选取数组中的数组中的一个数字 - 递归的作用：选取下一个数字，也就是进入你图中的第二层
那么剩下的，也只有循环中递归代码之前和之后的部分了，其功能简单来说：在递归之前，将选择的数字加入了数组，在递归之后，将选择的数字移出去了数组。需要理解的一点是，递归之前的代码，是为了本次做准备，递归之后的代码，则是为了下次做准备，这也是为何要在递归之后进行移除的原因。
简单模拟：
# [1,2,3,4]中取两个数
首次循环开始：
nums[i]为1，取1后开始递归，
选取下一个数字，将会取 [2,3,4] （因为1取过之后使用used[i]进行了标记）
第二次循环开始：
nums[i]为2，取2后开始递归
但是取2之前需要将递归之前取的1删掉，因为每次只能取一个数，进入递归之后才会取下一个数
...如上，望能理解~
发布于 2024-03-23 02:04・IP 属地江苏