1.前言
哈喽小伙伴们大家好哦~从今天开始笔者就要开始正式学习数据结构与算法了，在这里写知识博客既是做一些学习笔记，又相当于给大家做知识分享咯，希望大家一起加油哦！
2.正文
2.1递归的引入
在正式讲解递归之前，我们需要先介绍一个数学的知识——数学归纳法。大家可能会疑惑，数学归纳法和本文讲解的利用递归实现函数功能解决实际问题有什么关系呢？往下看即可：
2.1.1数学归纳法
数学归纳法是一种数学证明方法，主要用于证明某个给定命题在整个（或者局部）自然数范围内成立。
数学归纳法的原理在于：
- 首先证明在某个初始值（通常情况下是参数n取1，但也不是必须的）时命题成立。
- 然后证明可以从任意一个值的成立推导出下一个值也成立。当这两点都已经证明，就可以通过反复使用这个方法验证对所有的正整数都成立。
具体步骤包括：
- 验证n取第一个自然数时命题成立。
- 假设n=k时命题成立，然后以验证的条件和假设的条件作为论证的依据进行推导，证明当n=k+1时命题也成立（k代表任意自然数）。（在这个过程中，不能直接将n=k+1代入假设的原式中去这是常犯的错误之一）
示例：
- 证明1+2+3+...+n=n×(n+1)/2。首先，当n=1时，显然成立。
- 然后，假设当n=k时命题成立，即1+2+3+...+k=k×(k+1)/2，那么当n=k+1时，1+2+3+...+k+(k+1)=k×(k+1)/2+(k+1)=(k+1)×(k+2)/2，也成立。
- 依次递推，命题对于任意n都成立。
2.1.3数学归纳法与编程
#include<stdio.h> int main() { int sum = 0; for (int i = 1; i <= 100; i++) { sum += i; } printf("%d", sum); return 0; }我们按照上文的步骤来进行梳理：（虽然这段代码的思路和执行都一目了然，但是我们可以通过它很好的说明白问题）
- 当i=1时，sum等于1符合题意。
- 假设i-1成立，我们用f(i-1)来表示相加的总和，则显然f(i)=f(i-1)+i（i大于1小于等于100时），得证。
- 依次递推，该结构逻辑严密
由此我们便完成了数学归纳法在编程上的思想体现。
2.1.3数学归纳法与递归
递归基本原理是通过直接或间接地调用自身算法的过程来解决问题。递归算法通常包括一个或多个基本情况（即不需要递归就能直接求解的情况）和一个或多个递归情况（即需要调用自身算法来求解的情况）。
而根据我们上文讲述的数学归纳法，都利用了问题的逐步分解和递推求解的思路。我们都通过对问题的逐步分解和递推求解来解决更小的子问题。
由此，我们在利用递归思想建立函数时就可以采用这样的分析方式来进行分析。
- 给递归函数一个明确的语义（要明确是要做什么的）
- 实现边界条件时的程序逻辑
- 假设递归函数调用返回结果是正确的，实现本层函数逻辑（逐步分解，最终变成一个小问题）
2.2递归的简单实现
2.2.1路飞吃桃
题目描述
路飞买了一堆桃子不知道个数，第一天吃了一半的桃子，还不过瘾，又多吃了一个。以后他每天吃剩下的桃子的一半还多一个，到 n 天只剩下一个桃子了。路飞想知道一开始买了多少桃子。
输入描述
输入一个整数 n(2≤n≤30)。
输出描述
输出买的桃子的数量。
示例
代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n = 0;
int solve(int x) {
if (x == 1)return 1;
else return 2 * (solve(x - 1) + 1);
}
int main() {
cin >> n;
int ans = solve(n);
cout << ans << endl;
return 0;
}这道题虽然很基础，但却将递归的简单实现体现的淋漓尽致，具体不详解。
2.2.2弹簧板
题目描述
有一个小球掉落在一串连续的弹簧板上，小球落到某一个弹簧板后，会被弹到某一个地点，直到小球被弹到弹簧板以外的地方。
假设有 n 个连续的弹簧板，每个弹簧板占一个单位距离，a[i] 代表代表第 i 个弹簧板会把小球向前弹 a[i] 个距离。比如位置 1 的弹簧能让小球前进 2 个距离到达位置 3 。如果小球落到某个弹簧板后，经过一系列弹跳会被弹出弹簧板，那么小球就能从这个弹簧板弹出来。
现在小球掉到了1 号弹簧板上面，那么这个小球会被弹起多少次，才会弹出弹簧板。 1号弹簧板也算一次。
输入描述
第一个行输入一个 n 代表一共有 n(1≤n≤100000)个弹簧板。
第二行输入 n 个数字，中间用空格分开。第 i 个数字 a[i](0<a[i]≤30) 代表第 i 个弹簧板可以让小球移动的距离。
输出描述
输出一个整数，表示小球被弹起的次数。
示例
代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N = 1e6;
int a[N];
int n,ans;
int solve(int x, int a[N],int n) {
if (x >= n)return 0;
else return solve(x + a[x], a, n) + 1;
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
ans = solve(0, a, n);
cout << ans << endl;
return 0;
}当然这里可以用vector容器简单改进一下，可以降低空间复杂度。
vector和普通数组的区别：
1.数组是静态的，长度不可改变，而vector可以动态扩展，增加长度
2.数组内数据通常存储在栈上，而vector中数据存储在堆上
push_back函数是用于在vector容器末端添加一个数
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
const int N = 1e6;
vector <int>a;
int n=0,ans;
int solve(int x, vector <int>&a, int n){
if (x >= n)return 0;
else return solve(x + a[x], a, n) + 1;
}
int main() {
cin >> n;
for (int i = 0, m; i < n; i++) {
cin >> m;
a.push_back(m);
}
ans = solve(0, a, n);
cout << ans << endl;
return 0;
}2.2.3递归实现指数型枚举
题目描述
从 1−n 这 n 个整数中随机选取任意多个，每种方案里的数从小到大排列，按字典序输出所有可能的选择方案。
输入描述
输入一个整数 n。（1≤n≤10）
输出描述
每行一组方案，每组方案中两个数之间用空格分隔。
注意每行最后一个数后没有空格。
示例
在正式做提前，先弄清楚一个概念，何为字典序？
字典序是一个按照字典顺序排列元素的方式。在字典序中，元素按照它们在字典中的顺序进行排序，即按照字符或数字的自然顺序排列。
在字符串中，字典序就是按照字母表的顺序来排列字符串。如果两个字符串长度不同，较短的字符串会在较长的字符串之前。如果两个字符串的前几个字符相同，那么它们将按照下一个字符的顺序进行排序，以此类推。
代码
#include <iostream>
using namespace std;
int arr[10];
void func(int n) {
for (int i = 0; i <= n; i++) {
if (i) cout << " ";
cout << arr[i];
}
cout << endl;
return ;
}
void f(int i, int j, int n) {
if (j > n) return ;
for (int k = j; k <= n; k++) {
arr[i] = k;
func(i);
f(i + 1, k + 1, n);
}
return ;
}
int main() {
int n;
cin >> n;
f(0, 1, n);//分别用来记录位置，所填入的数字，以及最大数
return 0;
}2.2.4递归实现组合型枚举
题目描述
从 1−n 这 n 个整数中随机选取 m 个，每种方案里的数从小到大排列，按字典序输出所有可能的选择方案。
输入描述
输入两个整数 n,m。（1≤m≤n≤10）
输出描述
每行一组方案，每组方案中两个数之间用空格分隔。
注意每行最后一个数后没有空格。
示例
代码
#include <iostream>
using namespace std;
int arr[10];
void print_one_result(int n) {
for (int i = 0; i < n; i++) {
if (i) cout << " ";
cout << arr[i];//解决空格问题
}
cout << endl;
return;
}
void f(int i, int j, int n, int m) {
if (i == m) {
print_one_result(m);//单独创建打印函数
return;
}
//俩个判断条件一个是不要超过指定数量，另一个是后面剩下的数字要大于等于还需要的数字
for (int k = j; k <= n && m - i - 1 <= n - k; k++){
arr[i] = k;
f(i + 1, k + 1, n, m);//核心递归部分
}
return;
}
int main() {
int n, m;
cin >> n >> m;
f(0, 1, n, m);//分别记录最小数，最大数，指定的枚举最大值以及要枚举多少位
return 0;
}2.2.5递归实现排列型枚举
题目描述
从 1−n 这 n 个整数排成一排并打乱次序，按字典序输出所有可能的选择方案。
输入描述
输入一个整数 n。（1≤n≤8）
输出描述
每行一组方案，每组方案中两个数之间用空格分隔。
注意每行最后一个数后没有空格。
示例
代码
#include <iostream>
using namespace std;
int arr[10], vis[10] = { 0 };
void print_one_result(int n) {
for (int i = 0; i < n; i++) {
if (i) cout << " ";
cout << arr[i];
}
cout << endl;
return;
}
void f(int i, int n) {
if (i == n) {
print_one_result(n);
return;
}
for (int k = 1; k <= n; k++) {
if (vis[k]) continue;
arr[i] = k;
vis[k] = 1;
f(i + 1, n);
vis[k] = 0;
}
return;
}
int main() {
int n;
cin >> n;
f(0, n);
return 0;
}3.小结
今天数据结构第一讲：递归函数的设计技巧到这里就结束了，希望喜欢的朋友多多支持我哦~（敲完了以后脑子快爆炸了）
