首先,理解递归。众所周知,人脑的栈是有限且远远达不到计算机的水平的,所以,要想在大脑中或者通过纸笔一层层的模拟理解递归,最终的结果只有一个,就是把自己绕在里面。理解递归的第一步,就是要纵观全局。
理解递归
理解递归最好的方案就是二叉树的遍历,要完成一棵二叉树的遍历,最简单的实现莫过于递归的方式了,以力扣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 属地江苏