文章目录
- 一. 什么是递归
- 1.1. 递归的定义
- 1.2. 何时使用递归
- 1.3. 递归模型
- 二. 递归算法的设计
- 2.1. 递归算法设计的步骤
- 2.2. 基于递归数据结构的递归算法设计
- 2.3. 基于递归求解方法的递归算法设计
- 三. 递归总结
- 3.1. 递归技术总结
- 3.2. 递归算法设计总结
- 3.3. 递归函数设计中几个问题
一. 什么是递归
1.1. 递归的定义
- 递归的定义：
- 尾递归：
1.2. 何时使用递归
- 在以下三种情况，常常要用到递归的方法：
1.3. 递归模型
- 下面的例子： 统计全国GDP这个大问题转化为北京市，上海市。然后又继续划分，直到某个企业。
- 斐波那契数列：
#include <iostream>
using namespace std;
int fib(int n)
{
if (n == 1 || n == 2) //递归出口
return 1;
else //递归体
return fib(n - 1) + fib(n - 2);
}
int main()
{
int n = 6;
cout << fib(n) << endl;
system("pause");
return 0;
}
- 输出结果：
8
请按任意键继续. . .
二. 递归算法的设计
2.1. 递归算法设计的步骤
- 下面的例子：
#include <iostream>
#include <vector>
using namespace std;
float f(vector<float> &arr, int i)
{
float m;
if (i == 0)
return arr[0];
else
{
m = f(arr, i - 1);
return m > arr[i] ? arr[i] : m;
// if (m > arr[i])
// return arr[i];
// else
// return m;
}
}
int main()
{
vector<float> arr = {1, 2.2, 3, 5, 8, 9, 10, 3.3, 0.5};
cout << f(arr, arr.size() - 1) << endl;
system("pause");
return 0;
}
- 输出结果：
0.5
请按任意键继续. . .
2.2. 基于递归数据结构的递归算法设计
- 下面的例子：
#include <iostream>
using namespace std;
typedef int ElemType; //简单的数据元素类型
typedef struct LNode //单链表结点类型
{
ElemType data; //数据域
LNode *next; //指针域：指向直接后继结点
} LNode, *LinkList;
// =============================给数据域赋值====================================
void input(ElemType *ep) //实现数据域元素输入的定制函数
{
cout << "input the data of linklist: ";
cin >> *ep; //在函数中可以写更加复杂、任意形式、任意数目的输入
}
// =============================1. 头插法创建单链表=============================
// LinkList *L：相当于LNode **L是一个指针，L存放的类型是LinkList(指针类型)，就只指针的指针。
void createLinkF(LinkList *L, int n, void (*input)(ElemType *))
{ //头插法创建单链表，调用input输入函数输入数据
LinkList s;
*L = new LNode; //创建头结点,把这个节点的地址赋值给指针*L
(*L)->next = NULL; //初始时为空表
for (; n > 0; n--) //创建n个结点链表
{
s = new LNode; //创建新结点
input(&s->data); //调用input输入数据域
s->next = (*L)->next; //将s增加到开始结点之前
(*L)->next = s;
}
}
// ==================================2. 打印链表=================================
void printLinkList(LinkList s)
{
while (s != NULL)
{
cout << s->data << " ";
s = s->next;
}
}
// +++++++++++++++++++++++++++++ 求单链表中数据节点 +++++++++++++++++++++++++++++++
int count(LinkList s)
{
if (s == NULL)
return 0;
else
return count(s->next) + 1;
}
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
int main()
{
LinkList L;
int n;
cout << "input the length of linklist: ";
cin >> n;
//L本身已经是一个指针，&L指针变量的地址作为实参传递；那么用来接收的应该是一个指针的指针。
createLinkF(&L, n, input);
printLinkList(L->next); //去掉头结点；
cout << "\nthe length of linklist(count): ";
cout << count(L->next) << endl;
system("pause");
return 0;
}
input the length of linklist: 5
input the data of linklist: 22
input the data of linklist: 33
input the data of linklist: 44
input the data of linklist: 12
input the data of linklist: 24
24 12 44 33 22
the length of linklist(count): 5
请按任意键继续. . .
#include <iostream>
using namespace std;
typedef int ElemType; //简单的数据元素类型
typedef struct LNode //单链表结点类型
{
ElemType data; //数据域
LNode *next; //指针域：指向直接后继结点
} LNode, *LinkList;
// =============================给数据域赋值====================================
void input(ElemType *ep) //实现数据域元素输入的定制函数
{
cout << "input the data of linklist: ";
cin >> *ep; //在函数中可以写更加复杂、任意形式、任意数目的输入
}
// =============================1. 头插法创建单链表=============================
// LinkList *L：相当于LNode **L是一个指针，L存放的类型是LinkList(指针类型)，就只指针的指针。
void createLinkF(LinkList *L, int n, void (*input)(ElemType *))
{ //头插法创建单链表，调用input输入函数输入数据
LinkList s;
*L = new LNode; //创建头结点,把这个节点的地址赋值给指针*L
(*L)->next = NULL; //初始时为空表
for (; n > 0; n--) //创建n个结点链表
{
s = new LNode; //创建新结点
input(&s->data); //调用input输入数据域
s->next = (*L)->next; //将s增加到开始结点之前
(*L)->next = s;
}
}
// +++++++++++++++++++++++++++++ 正向显示单链表中的值 +++++++++++++++++++++++++++++
void traverse(LinkList s)
{
if (s == NULL)
return;
cout << s->data << " ";
traverse(s->next);
}
// +++++++++++++++++++++++++++++ 反向显示单链表中的值 +++++++++++++++++++++++++++++
void traverse_R(LinkList s)
{
if (s == NULL)
return;
traverse_R(s->next);
cout << s->data << " ";
}
int main()
{
LinkList L;
int n;
cout << "input the length of linklist: ";
cin >> n;
//L本身已经是一个指针，&L指针变量的地址作为实参传递；那么用来接收的应该是一个指针的指针。
createLinkF(&L, n, input);
cout << "traverse:";
traverse(L->next); //去掉头结点；
cout << "\ntraverse_R:";
traverse_R(L->next);
system("pause");
return 0;
}
input the length of linklist: 4
input the data of linklist: 1
input the data of linklist: 2
input the data of linklist: 3
input the data of linklist: 4
traverse:4 3 2 1
traverse_R:1 2 3 4
请按任意键继续. . .
2.3. 基于递归求解方法的递归算法设计
- 下面的例子：
三. 递归总结
3.1. 递归技术总结
3.2. 递归算法设计总结
3.3. 递归函数设计中几个问题
