『数据结构与算法』解读递归算法！

tech2024-12-09 9

解读递归算法！本文章属于数据结构与算法专栏系列，欢迎关注，链接: 数据结构与算法。文章会持续更新，希望大家多点赞收藏加转发！专栏文章总目录链接：数据结构与算法！

文章目录

一. 什么是递归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 请按任意键继续. . .