devbox
2023面试高手
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【日常系列】赏析《递归从入门到精通》（C++版）

作者：2023面试高手 | 2024-05-28 21:26:31

赞

踩

【日常系列】赏析《递归从入门到精通》（C++版）

递归从入门到精通

（Ⅰ）递归入门

编写一个递归函数

  • 这个递归函数的功能是什么，怎样调用这个函数，即设计好递归函数的返回值和参数列表
  • 什么时候应该结束这个递归，它的边界条件（出口）是什么 （边界条件）
  • 在非边界情况时，怎样从第n层转变成第n+1层 (递推公式)

1.1递归之计算阶乘(factorial)

n ! = { 1 n = 0 n ∗ ( n − 1 ) ! n > 0 n!=

{1n=0n∗(n−1)!n>0
n!={1n∗(n−1)!​n=0n>0​

#include <stdio.h>

int fact(int n) {
    if (n == 0) return 1;//边界
        return n * fact(n - 1);//公式
}

int main() {
    int ans = fact(10); //调用
    printf("%d\n", ans);
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

1.2.递归之计算斐波那契数列(fib)

Fibonacci sequence：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ……
f ( n ) = { 0 n = 0 1 n = 1 f ( n − 2 ) + f ( n − 1 ) n > 1 f(n)=

{0n=01n=1f(n−2)+f(n−1)n>1
f(n)=⎩⎪⎨⎪⎧​01f(n−2)+f(n−1)​n=0n=1n>1​

#include <stdio.h>

int fib(int n) {
	if (n == 0) return 0;
	if (n == 1) return 1;
	return fib(n - 1) + fib(n - 2);
}

int main() {
	for (int i = 0;i < 10;i++) {
		printf("%d ", fib(i));
	}
	printf("\n");
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

1.3.递归之计算最大公约数(greatest common divisor)

gcd(12, 32) = 4

gcd(a,   b)
gcd(32,  12)
gcd(12,  8)
gcd(8,   4)
gcd(4,   0)

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

g c d ( a , b ) = { a b = 0 g c d ( b , a % b ) b ≠ 0 gcd(a,b)=

{ab=0gcd(b,a%b)b≠0
gcd(a,b)={agcd(b,a%b)​b=0b​=0​

//辗转相除法
#include <stdio.h>
int gcd(int a, int b) {
	if (b == 0)return a;
	return gcd(b, a % b);
}

int main() {
	printf("%d ", gcd(12, 32));
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

分治算法

分治法的设计思想：

  1. 分–将问题分解为规模更小的子问题；
  2. 治–将这些规模更小的子问题逐个击破；
  3. 合–将已解决的子问题合并，最终得出“母”问题的解；
  • 减而治之（每次让问题的规模减1）
  • 分而治之（每次让问题的规模减半）（归并排序的思想）

1.4递归之楼梯总跳法（减而治之-问题规模逐减一）

题目描述：
一个台阶总共有n级，如果一次可以跳1级，也可以跳2级。求总共有多少总跳法。
第一行输入T，表示有多少个测试数据。接下来T行，每行输入一个数n，表示台阶的阶数。
输出时每一行对应一个输出。

样例输入：
3
5
8
10

样例输出：
8
34
89

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

解析：

f ( n ) = { 1 n = 1 2 n = 2 f ( n − 1 ) + f ( n − 2 ) n > 2 f(n)=

{1n=12n=2f(n−1)+f(n−2)n>2
f(n)=⎩⎪⎨⎪⎧​12f(n−1)+f(n−2)​n=1n=2n>2​

参考代码：

#include <stdio.h>

int solve(int n) {
	if (n == 1) return 1;
	if (n == 2) return 2;
	//列如：solve(5)
	//从1->2级：即先采用‘跳一级’策略，后面4级台阶的总跳法为solve(4)个
	//从1->3级：即先采用‘跳两级’策略，后面3级台阶的总跳法为solve(3)个
	return solve(n - 1) + solve(n - 2);
}

int main() {

	//int T;
	//scanf_s("%d", &T);//设置测试数
	//while (T--) {
	//	int n;
	//	scanf_s("%d", &n);//设置台阶数
	int ans = solve(5);
	printf("%d\n", ans);
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

1.5递归之排序问题（分而治之-问题规模逐减半）

在这里插入图片描述

#include   <iostream>
using  namespace std;


void mergeArray(int A[], int l, int mid, int r) {
	int* temp = new int[r - l + 1];
	int i = l, j = mid + 1;//i指向‘前半段’首索引，j指向‘后半段’首索引
	int k = 0;//临时temp[]首索引

	//给临时temp[]赋‘A[]前半段’
	while (i <= mid && j <= r) {
		if (A[i] <= A[j])temp[k++] = A[i++];
		else temp[k++] = A[j++];
	}
	//给临时temp[]赋‘A[]后半段’
	while(j <= r)temp[k++] = A[j++];
	while (i <= mid)temp[k++] = A[i++];

	//通过临时temp[]赋A[],使A[]得到真正排序
	
	for (int i = l, k = 0;i <= r;i++, k++) {
		A[i] = temp[k];
	}
	delete temp;
}



//归并排序
void mergesort(int A[], int l, int r) {
	if (l >= r) return;
	int mid = l + (r - l) / 2;
	mergesort(A, l, mid);左半区间[lo, mid] 排好序
	mergesort(A, mid+1, r);右半区间[mid + 1, hi] 排好序
	mergeArray(A, l, mid, r);//进行合并
}


int main() {
	int A[] = { 6,1,2,9,7,3 };
	int N = sizeof(A) / sizeof(int);

	mergesort(A, 0, N - 1);
	for (int x : A) {
		cout << x << " ";
	}
	cout << endl;
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49

（Ⅱ）二叉树、树

二叉树的遍历

先序遍历

请添加图片描述

中序遍历

请添加图片描述

二叉树节点在水平方向上的投影顺序即为中序遍历的顺序。

后序遍历

请添加图片描述

层次遍历

请添加图片描述

2.1递归之求二叉数高度
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;



struct Node {
	int data;
	Node * lchild, * rchild;
	Node(int x = 0) { data = x;lchild = rchild = NULL; }
	
	void setChildNode(Node *l,Node *r) {
		lchild = l;
		rchild = r;
	}		
};

void preorderTrav(Node * root){
	if (root == NULL)return;
	printf("%d", root->data);//先序遍历：先访问根节点
	preorderTrav(root->lchild);
	preorderTrav(root->rchild);
 }

void inorderTrav(Node * root) {
	if (root == NULL)return;
	inorderTrav(root->lchild);
	printf("%d", root->data);//中序遍历：中间访问根节点
	inorderTrav(root->rchild);
}

void postoderTrav(Node* root) {
	if (root == NULL)return;
	postoderTrav(root->lchild);
	postoderTrav(root->rchild);
	printf("%d", root->data);//后序遍历：最后访问根节点
}
//层次遍历讲解：https://www.bilibili.com/video/BV1S54y1Y7Uq?from=search&seid=2361716283609621762&spm_id_from=333.337.0.0
//         A
//	  B            C
//D      E     F     G

//层次遍历（有条件的先序遍历，key：*t<=>Node[N]；从而更好的访问不断变化的队顶元素）
void levelTrav(Node* root) {
	if (root == NULL)return;
	
	//建立队列Q
	queue <Node*> Q;
	
	//根节点入队('A')
	Q.push(root);
	//循环出队,入队===================================>⑤当队列为空时返回true，退出循环
	while (Q.empty() != true) {
		//访问队顶元素①('A')====>②('B')====>③('C')====>④('DEFG')
		Node *t = Q.front();
		//移除并打印队顶元素①('A')====>②('B')====>③('C')====>④('DEFG')
		Q.pop();
        printf("%d", t->data);
		
		//左子树入队①('B')====>②('D')====>③('F')====>④pass
		if (t->lchild != NULL)Q.push(t->lchild);
		//右子树入队①('C')====>②('E')====>③('G')====>④pass
		if (t->rchild != NULL)Q.push(t->rchild);
	}
	printf("\n");
}




int getTreeHigh(Node* root) {
	if (root == NULL)return 0;
	int LHigh = getTreeHigh(root->lchild);
	int RHigh = getTreeHigh(root->rchild);
	return max(LHigh, RHigh)+1;
}




int main() {
	Node *root = new Node(1);
	Node * Node2 = new Node(2);
	Node * Node3 = new Node(3);
	Node * Node4 = new Node(4);
	Node * Node5 = new Node(5);
	Node * Node6 = new Node(6);
	Node * Node7 = new Node(7);
	Node * Node8 = new Node(8);
	   //        1
    //      2              3
    //  4      5       null   7
  //null 8    6  null        
	root->setChildNode(Node2, Node3);
	Node2->setChildNode(Node4, Node5);
	Node3->setChildNode(NULL, Node7);
	Node4->setChildNode(NULL, Node8);
	Node5->setChildNode(Node6, NULL);


	preorderTrav(root);
	printf("\n");
	inorderTrav(root);
	printf("\n");
	postoderTrav(root);
	printf("\n");

	levelTrav(root);
	printf("\n");

	printf("Tree Height: %d\n", getTreeHigh(root));
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113

在这里插入图片描述

2.2递归之表达式树的输出与求值

表达式树的特征：叶节点是运算数，非叶节点一定是运算符!
在这里插入图片描述

输入格式：

第一行给出节点的个数N，每个节点的编号为0 ~ N-1

接下来N行每行分别给出：

​ 该节点的编号、该节点的操作数/操作符、该节点的左孩子编号、右孩子编号（-1表示NULL）

输出格式：

第一行输出该表达式树的中缀表达式，该用括号的地方需要用括号括起来。

第二行输出该表达式树的前缀表达式。

第二行输出该表达式树的后缀表达式。

第四行输出该表达式树的计算结果，保留两位小数。

样例输入：

11
0 - 1 2
1 + 3 4
2 / 5 6
3 4 -1 -1
4 * 7 8
5 6 -1 -1
6 3 -1 -1
7 1 -1 -1
8 - 9 10
9 5 -1 -1
10 2 -1 -1

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

样例输出：

(4+(1*(5-2)))-(6/3)
- + 4 * 1 - 5 2 / 6 3
4 1 5 2 - * + 6 3 / -
5.00

  • 1
  • 2
  • 3
  • 4

完整代码：

#include <iostream>
using namespace std;
//二叉树组成：运算数（叶结点）+运算符（其他）
struct Node{
	char data;
	Node* lchild, * rchild;
};

//前缀表达式（前序遍历）
void preOrder(Node* root) {	
	if (root == NULL) return;
	printf("%c ", root->data);
	preOrder(root->lchild);
	preOrder(root->rchild);
}
//后缀表达式（后续遍历）
void postOrder(Node *root) {
	if (root == NULL) return;
	postOrder(root->lchild);
	postOrder(root->rchild);
	printf("%c ", root->data);
}

//中缀表达式（有条件的中序遍历）
void inOrder(Node *root,int layer){
	if (root == NULL)return;
    //输出目标结果：(4 + (1 * (5 - 2))) - (6 / 3)
    //注释：若无此条件语句，输出结果：((  (4)+(  (1)*(  (5)-(2)  )))-(  (6)/(3)  ));
	if (root->lchild == NULL && root->rchild == NULL) printf("%c", root->data);//操作对象：叶结(束)点
	else {
		if (layer > 0)printf("(");
	//注释：若无此（int layer）参数引入，输出结果：((  4+(  1*(  5-2  )))-(  6/3  ));
		inOrder(root->lchild,layer+1);
		printf("%c",root->data);
		inOrder(root->rchild,layer+1);
		if (layer > 0)printf(")");
	}
}




//计算函数
double calc(double a, double b, char op) {
	switch (op){
	case '+':return a + b;
	case '-':return a - b;
	case '*':return a * b;
	case '/':return a / b;
	}
}
//递归算法:返回计算结果
double calcExprTree(Node *root) {
	if (root == NULL)return 0;
	//当递到最后一层（递归边界条件）：即全是叶结点时,‘5’->5,'2'->2;
	if (root->lchild == NULL && root->rchild == NULL)return root->data - '0';//对象：叶结点
	double a = calcExprTree(root->lchild);
	double b = calcExprTree(root->rchild);
	//计算5-2，并开始归，归到到第一层，返回最终结果；
	return calc(a, b, root->data);
}




//自定义交互界面：&索引0-10；&对应索引元素值；
		//&对应索引的左子节点索引（-1代表NULL）；&对应索引的右子节点索引（-1代表NULL）；
		//样例输入（在自定义交互界面):
		//	    11
		//		0(空格)-(空格)1(空格)2
		//		1 + 3 4
		//		2 / 5 6
		//		3 4 - 1 - 1
		//		4 * 7 8
		//		5 6 - 1 - 1
		//		6 3 - 1 - 1
		//		7 1 - 1 - 1
		//		8 - 9 10
		//		9 5 - 1 - 1
		//		10 2 - 1 - 1
		//      样例输出：
		//        (4 + (1 * (5 - 2))) - (6 / 3)(中缀表达式)
		//		- +4 * 1 - 5 2 / 6 3（前缀表达式）
		//		4 1 5 2 - *+6 3 / -（后缀表达式）
		//		5.00

int main() {
	//通过用户交互界面，定义总节点数N（含根节点）；
	int N;
	scanf("%d/n", &N);
	
	//*nodes[N]<=>树结构Node[索引及对应元素值]；
	Node* nodes = new Node[N];
	
	//赋值*nodes[N]：通过循环结构及用户交互界面；
	for (int i = 0;i < N;i++) {
		int index;
		char data;
		int l, r;
		//用户交互界面;
		scanf("%d %c %d %d",&index, &data, &l, &r);
		
		//赋值;
		nodes[index].data = data;
		nodes[index].lchild = (l != -1 ? &nodes[l] : NULL);
		nodes[index].rchild = (r != -1 ? &nodes[r] : NULL);
	}
	Node *root = &nodes[0];
	


	inOrder(root, 0);
	printf("\n");

	preOrder(root);
	printf("\n");

	postOrder(root);
	printf("\n");


	double ans = calcExprTree(root);
	printf("%.2f\n",ans);

	return 0;

}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
2.3递归之求某节点到根节点的路径

对于如下二叉树，节点7位于第4层，其到跟节点的路径为1 2 5 7

在这里插入图片描述

求某节点所在层数

先把问题简化一下，求二叉树指定节点所在层数（假设根节点的层数为1）

为了记录当前访问节点的层号，对于层号，可以采用以下两种方式：

在这里插入图片描述

求节点路径

在这里插入图片描述

在这里插入图片描述

完整代码

对于如下二叉树，节点7位于第4层，其到跟节点的路径为1 2 5 7

在这里插入图片描述

#include <iostream>
#include <vector>
using namespace std;

struct Node {
	int data;
	Node* lchild, * rchild;
	
	Node(int x = 0) { data = x;lchild = rchild = NULL; }

	void setChildNode(Node* l, Node* r) {
		lchild = l;
		rchild = r;
	}
};

/求该节点所在层数///
//方法一：使用全局变量(int layer=0;堆空间)

int layer = 0;//key1
bool flag1 = false;
//前序遍历架构
void getNodeLayer(Node* root, int x) {
	if (root == NULL)return;
	
	//找到x后，flag1用于提前结束递归执行；
	if (flag1)return;
	//根节点层为1；
	layer++;//key2
	if (root->data == x) {
		printf("%d\n", layer);
		flag1 = true;
		return;
	}
	getNodeLayer(root->lchild, x);
	getNodeLayer(root->rchild, x);

	//每次遍历到末尾，层数减一；再进行到下次遍历，层数再依次加一
	layer--;//key3
}

//方法二：使用函数传参（值传递:getNodeLayer(root, x, layer + 1) );
// getNodeLayer(root, 7, 1);//key1

//bool flag1 = false;
//void getNodeLayer(Node* root, int x, int layer) {//key2
//	if (root == NULL)return;
//
//	if (flag1 == true)return;
//	if (root->data == x) {
//		printf("%d", layer);
//		flag1 = true;
//		return;
//	}
//	getNodeLayer(root->lchild, x, layer + 1);//key3
//	getNodeLayer(root->rchild, x, layer + 1);//key4
//}





//方法三：使用函数传参（传指针/引用:int &layer栈空间)（了解）

//bool flag1 = false;
//void getNodeLayer(Node* root, int x, int & layer) {//key3
//	if (root == NULL)return;
//
//	layer++;//key4
//	if (root->data == x) {
//		printf("%d", layer);
//		flag1 = true;
//		return;
//	}
//	getNodeLayer(root->lchild, x, layer);
//	getNodeLayer(root->rchild, x, layer);
//
//	layer--;//key5
//}

//方法四：将递归函数封装（了解）
//void getNodeLayer(Node *root, int x, int &layer, int &ans, bool &flag1) {//key3
//	if (root == NULL)return;
//
//	layer++;//key4
//	if (flag1 == true)return;
//	if (root->data == x) {
//		ans = layer;
//		flag1 = true;
//		return;
//	}
//	getNodeLayer(root->lchild, x, layer, ans, flag1);
//	getNodeLayer(root->rchild, x, layer, ans, flag1);
//
//	layer--;//key5
//}
//int getNodeLayer(Node* root, int x) {
// //key1（定义引用变量）
//	int ans;
//	int layer = 0;
//	bool flag1= false;
key2
//	getNodeLayer(root, x,layer,ans, flag1);
// //key6（输出“接口”）
//	return ans;
//}


/求节点路径（类似求该节点所在层数）
//方法一：使用全局数组

vector<int>path;//key1全局数组

bool flag2 = false;
void getNodePath(Node* root, int x) {
	if (root == NULL)return;
	
	if (flag2)return;
	path.push_back(root->data);//key2入栈
	if (root->data == x) {
		for (int x : path) {C++11特性：范围的For循环（range-based-for）
			printf("%d ", x);//key3输出栈
		}
		flag2 = true;
		return;
	}
	getNodePath(root->lchild, x);
	getNodePath(root->rchild, x);

	path.pop_back();//key4出栈
}

//方法二：使用函数传参（传指针/引用）

//bool flag2 = false;
//void getNodePath(Node* root, int x, vector<int>& path) {//key3 指针数组
//	if (root == NULL)return;
//
//	if (flag2)return;
//	path.push_back(root->data);//key4
//	if (root->data == x) {
//		for (int x : path) {
//			printf("%d ", x)；//key5
//		}
//      flag2 = true;
//		return;
//	}
//	getNodePath(root->lchild, x, path);
//	getNodePath(root->rchild, x, path);
//
//	path.pop_back();//key6
//}



//方法三：使用函数传参（值传递） 不推荐（∵每次递归调用，会对path数组进行复制∴时间和空间效率低）

//bool flag2 = false;
//void getNodePath(Node* root, int x, vector<int>path) {//key3
//	if (root == NULL)return;
//
//	if (flag2)return;
//	path.push_back(root->data);
//	if (root->data == x) {
//		for (int x : path) {
//			printf("%d ", x);
//       }//key4
//		flag2 = true;
//		return;
//	}
//	getNodePath(root->lchild, x, path);
//	getNodePath(root->rchild, x, path);
//	//无path.pop_bach()
//}


int main() {
	Node* root = new Node(1);
	Node* node_2 = new Node(2);
	Node* node_3 = new Node(3);
	Node* node_4 = new Node(4);
	Node* node_5 = new Node(5);
	Node* node_6 = new Node(6);
	Node* node_7 = new Node(7);
	Node* node_8 = new Node(8);

	root->setChildNode(node_2, node_3);
	node_2->setChildNode(node_4, node_5);
	node_3->setChildNode(NULL, node_6);
	node_5->setChildNode(node_7, NULL);
	node_7->setChildNode(NULL, node_8);

/求该节点所在层数/
//方法一
	int x = 7;
	getNodeLayer(root, x);
	
//方法二
	//getNodeLayer(root, 7，1);
	
//方法三
	//int layer=0;//key1
	// getNodeLayer(root, 7，layer);//key2
	
//方法四
	//int getNodeLayer(Node * root, int x) {
	// //key1(定义引用变量)
	//	int ans;
	//	int layer = 0;
	//	bool flag1 = false;
	// //key2
	//	getNodeLayer(root,x,layer,ans,flag1)
	//}
	// 
/求节点路径（类似求该节点所在层数）
//方法一
	getNodePath(root, x);
	printf("\n");
	
//方法二
	//key1定义引用变量
	//int x = 7;
	//vector<int>path;
	key2
	//getNodePath(root, x, path);
	
//方法三
	//key1
	//int x = 7;
	//vector<int>path;
	//key2
	//getNodePath(root, x, path);

	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215
  • 216
  • 217
  • 218
  • 219
  • 220
  • 221
  • 222
  • 223
  • 224
  • 225
  • 226
  • 227
  • 228
  • 229
  • 230
  • 231
  • 232
  • 233
  • 234
  • 235
写法一：vector<int> vec {1,2,3,4,5,6,7,8,9,10};
for (int i = 0; i < vec.size(); i++）{
    printf("%d ", vec[i]);
}
//C++11特性：范围的For循环（range-based-for）
写法二：for (int x : vec) {	//这样写对于容器内的每个元素是只读的
    printf("%d ", x);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
2.4递归之普通树的遍历

在这里插入图片描述

#include <iostream>
#include <vector>
#include <queue>
#include <initializer_list>
using namespace std;

struct Node {
	int data;
	//key1利用指针数组，存放多分支
	vector<Node*>child;

	Node(int x = 0) { data = x; }

	void setChildNode(initializer_list<Node*>list) {//C++11特性：initializer_list(传入列表数据，分别代表各分支节点)
		//key2利用循环及指针数组，建立多分支
		for (Node* x : list) {
			child.push_back(x);
		}
	}
};

//先序遍历
void preOrder(Node* root) {
	if (root == NULL)return;

	printf("%d", root->data);
	//key3利用循环及指针数组,进行递归
	for (Node* x : root->child) {
		preOrder(x);
	}
}
//后序遍历
void postOrder(Node* root) {
	if (root == NULL)return;
	//key3
	for (Node* x : root->child) {
			preOrder(x);
		}
	printf("%d", root->data);
	
}





//层次遍历
void levelOrder(Node* root) {
	if (root == NULL)return;

	queue<Node*> Q;//建队
	Q.push(root);//入队
	while(Q.empty() == false) {
		Node* t = Q.front();Q.pop();//出队
		//key4：利用*t<=>Node*,来进行队顶元素的变换
		printf("%d", t->data);//打印队顶节点元素
	    for (Node* x : t->child) {
		Q.push(x);//入队：相应队顶节点的子节点
		}
	}
}


int main() {
	Node* root = new Node(1);
	Node* node_2 = new Node(2);
	Node* node_3 = new Node(3);
	Node* node_4 = new Node(4);
	Node* node_5 = new Node(5);
	Node* node_6 = new Node(6);
	Node* node_7 = new Node(7);
	Node* node_8 = new Node(8);
	Node* node_9 = new Node(9);
	Node* node_10 = new Node(10);

	root->setChildNode({ node_2,node_3,node_4 });
	node_2->setChildNode({ node_5,node_6,node_7 });
	node_4->setChildNode({ node_8 });
	node_8->setChildNode({ node_9,node_10 });

	preOrder(root);
	printf("\n");

	postOrder(root);
	printf("\n");

	levelOrder(root);
	printf("\n");

	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91

递归调用原理

函数调用栈实例：主函数main()调用funcA()，funcA()调用funcB()，funcB()再自我调用（递归）

在这里插入图片描述

函数调用栈的基本单位是帧（frame）。每次函数调用时，都会相应地创建一帧， 记录该函数实例在二进制程序中的返回地址（return address），以及局部变量、传入参数等， 并将该帧压入调用栈。若在该函数返回之前又发生新的调用，则同样地要将与新函数对应的一帧压入栈中，成为新的栈顶。函数一旦运行完毕，对应的帧随即弹出，运行控制权将被交还给该函 数的上层调用函数，并按照该帧中记录的返回地址确定在二进制程序中继续执行的位置。

在任一时刻，调用栈中的各帧，依次对应于那些尚未返回的调用实例，亦即当时的活跃函数实例（active function instance）。特别地，位于栈底的那帧必然对应于入口主函数main()， 若它从调用栈中弹出，则意味着整个程序的运行结束，此后控制权将交还给操作系统。

此外，调用栈中各帧还需存放其它内容。比如，因各帧规模不一，它们还需记录前一帧的起始地址，以保证其出栈之后前一帧能正确地恢复。

作为函数调用的特殊形式，递归也可借助上述调用栈得以实现。比如在上图中，对应于 funcB()的自我调用，也会新压入一帧。可见，同一函数可能同时拥有多个实例，并在调用栈中 各自占有一帧。这些帧的结构完全相同，但其中同名的参数或变量，都是独立的副本。比如在 funcB()的两个实例中，入口参数m和内部变量i各有一个副本。

(Ⅲ)DFS/回溯算法

如果某问题的解可以由多个步骤得到，而每个步骤都有若干种选择（这些候选方案集可能会依赖之前做出的选择），且可以用递归枚举法实现，则它的工作方式可以用解答树来描述。

3.1回溯算法之全排列问题（深度优先搜索depth first search）

输出数字1~N所能组成的所有全排列

在这里插入图片描述

#include <iostream>
#include <vector>
using namespace std;
const int MAXn = 10;

bool isused[MAXn];//使用检验
vector<int>num;//设置num数组
int N;//数据范围（1-3）

void DFS(int index){
	//每次递归的边界条件
	if (index >= N) {
		for (int x : num) {
			printf("%d", x);
		}
		printf("\n");
		return;
    }


    //核心思想讲解：https://www.bilibili.com/video/BV1ct411u7Qi?from=search&seid=11426884062134919798&spm_id_from=333.337.0.0
	for (int i = 1;i <= N;i++) {
	if (isused[i])continue;
	//①1入队（index=0处）
	num.push_back(i);
	//②设置1已经used
	isused[i] = true;
	//③index=1->n-2做全排列
	DFS(index + 1);
	
	//④1出队
	num.pop_back();
	//⑤设置1未used
	isused[i] = false;
	}
}

int main() {
	N = 3;
	DFS(0);//输入0层
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42

素数环问题

将1到n这n个整数围成一个圆环，若其中任意2个相邻的数字相加，结果均为素数，那么这个环就成为素数环。

例如数字1-6所组成的一个素数环，用数组表示是[1, 4, 3, 2, 5, 6]（第一位固定为1）

在这里插入图片描述

在这里插入图片描述

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 100;

bool isPrimeNum[MAXN];/key1 质数检验 

bool isUsed[MAXN];//使用检验
vector<int> num;//ans数组
int N;//数据范围（1-4）
	  
	  
///key2 筛选法求质数
void getPrimeTable() {
	//先假设都是素数
	fill(isPrimeNum, isPrimeNum + MAXN, true);//设置拼接数组，值为true
	isPrimeNum[0] = isPrimeNum[1] = false;//并定义0，1为非质数

	for (int i = 2;i < MAXN;i++) {
		if (isPrimeNum[i]) {
			/key3 若i是质数：把i的倍数全部设置成非质数(质数的整数倍不是质数)；
			for (int j = i+i; j < MAXN;j += i) {//key2 j+=i;
				isPrimeNum[j] = false;
			}
		}
	}
}


void DFS(int index) {
	//递归边界条件
	if (index >= N) {
        key4 判断第一个数和最后一个数相加后是否为质数；
		int temp = num[0] + num[index - 1];key4-1 这里的index-1为尾元素索引；
		if (isPrimeNum[temp] == false)return;
		//若是：打印数组
		for (int x : num) {
			printf("%d", x);
		}
		printf("\n");
		return;
	}
	
	for (int i = 2;i <= N;i++) {
		if (isUsed[i])continue;
		
		//剪枝：若相邻元素和不为质数，直接跳出循环；
		int temp = i+ num[index - 1]; //key4-2 这里的index-1为相邻元素索引；
		if (isPrimeNum[temp] == false) {
			continue;
		}
		num.push_back(i);
		isUsed[i] = true;
		DFS(index + 1);

		num.pop_back();
		isUsed[i] = false;
	}
}


int main() {
	getPrimeTable();

	N = 4;
	num.push_back(1);

	DFS(1);


	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73

3.3回溯算法之八皇后问题（深度优先搜索depth first search）

八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当n = 1或n ≥ 4时问题有解。

在这里插入图片描述

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 100;
int solution[MAXN];//记录i行中皇后位置j
int cnt;//总方法数
int N;//N皇后


//key1 定义棋盘，以用于各种方法的可视化显示
char chessboard[MAXN][MAXN];
void printSolution() {
	fill(chessboard[0], chessboard[0] + MAXN * MAXN,'*');//初始化棋盘为*
	
	//通过for循环：查找棋盘上所有皇后位置j->定义所有皇后位置为#
	for (int i = 0;i < N;i++) {
		int j = solution[i];//查找：通过solution[i]，查找第i行中皇后位置j
		chessboard[i][j] = '#';//定义：查找后，定义皇后位置为#
		chessboard[i][N] = '\0';
	}
	printf("solution #%d\n", cnt);
	//通过for循环：打印*棋盘及所有#皇后
	for (int i = 0;i < N;i++) {
		printf("%s\n", chessboard[i]);//打印：*棋盘及#皇后
	}
	printf("\n");
}


//key2 判断（row，col）位置是否处在所有前皇后的攻击范围。若处于，则返回false；
bool judge(int row, int col) {
	//通过for循环：查找前row行所有皇后位置j，并判断（row，col）位置是否处于攻击位置
	for (int i = 0;i < row;i++) {
		//查找：通过solution[i]，查找第i行中皇后位置j
		int j = solution[i];
		//判断：同列、斜线(副对角、主对角)
		//注：不需要同行检查---在单层搜索的过程中，每一层递归，只会选for循环（也就是同一行）里的一个元素，所以不用去重了。）
		if (j == col || row + col == i + j || row - col == i - j)
			return false;
	}
	return true;
}


void DFS(int row) {
	//每次递归的边界条件
	if (row >= N) {
		cnt++;//成功递归一次，意味着多一种解法；
		printSolution();//可视化该解法
		return;
	}
	//核心
	for (int col = 0;col < N;col++) {
		//冲突：下循环
		if (judge(row, col) == false)continue;
		
		//不冲突：solution[row]=col,即定义第row行的皇后位置为col；
		solution[row] = col;
		DFS(row + 1);//每一层递归，只会选for循环（也就是同一行）里的一个元素
	}
}

int main() {
	N = 8;
	DFS(0);
	printf("N=%d,total solutions:%d\n", N, cnt);
	return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/2023面试高手/article/detail/639328
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号