甘肃龙网

  1. 首页 > 生活 > >

《数据结构》算法学习

生活百科递归

《数据结构》算法--递归与数学归纳法
递归与数学归纳法有着本质上的联系：
首先来了解一下数学上常见的函数、数列与程序中的函数之间的相互关系：
通过图表可以看出，两种思维方式是互通的，程序思维可以依托数学思维方式来实现，使问题变得更容易理解 。
1.数列
数列也是一种特殊的数学归纳法，其递推公式、前n项求和都体现了数学归纳法和递归的
思想 。
2.数学归纳法
步骤：（1）假设n = 1，结论成立；
（2）假设n = k时，结论成立，根据递推公式，求证n = k+1时结论也成立；
3.递归
步骤：（1）找递归出口，类似n = 1或初始化的状态；
（2） 找递归嵌套，同递推公式，找出第k项与第k-1项之间的关系；

《数据结构》算法学习

文章插图
（3）完成上面两步，再单纯考虑一个完整的算法周期的具体实现，后面的套娃让
程序自己去完成；
4.三者之间的关系如下表： 思想初始状态关系式相互关系
【《数据结构》算法学习】数列
a1 = k，（k为已知数）
an = f(a(n-1))
数列首项为递归入口，递推公式为递归的函数调用
数学归纳法
n=1时，结论成立
假设n=k时结论成立，证明n=k+1时结论也成立
n=1为递归入口，k-->k+1的论证关系为递归的函数调用
递归
入口（一般元素个数为1）
《数据结构》算法学习

文章插图
递归关系，函数一层层的调用
函数调用看作数列递推公式
5.示例
1：求数组的所有元素之和；
#include#include//3.定义好递归出口和嵌套公式之后，整段函数只是单纯考虑一个完整的算法周期的实现：//即把sum分割成arr[L]与ArrSum[arr, L+1, R]之和，这边正确实现之后，后面的套娃让程序自己去完成；//L为第一个元素位序，R为最后一个元素的位序；int ArrSum(int arr[], int L, int R){int sum;//1.递归出口，如同数学归纳法中初始状态：n=1的情况；if (L == R)sum = arr[L];else//2.递归嵌套，同递推公式，找出L和L+1的关系sum = arr[L] + ArrSum(arr, L+1, R);return sum;}int main(){int arr[5] = {5, 5, 5, 5, 10};int s = ArrSum(arr, 0, 4);printf("s = %d\n", s);return 0;}
2：求数组中所有元素的最大值；
#include#include/*int FindMax(int arr[], int len){int max = arr[0];for (int i=0; i max)max = arr[i];}return max;}*///3.两数比大小的具体实现，单纯考虑一个完整的算法周期的实现//L为第一个元素位序，R为最后一个元素的位序；int FindMax2(int arr[], int L, int R){//1.递归出口if (L == R)return arr[L];else{int a = arr[L];int b = FindMax2(arr, L+1, R);//2.把套娃第二层当做一个整体，与a进行比较if (a > b)return a;elsereturn b;}}int main(){int arr[10] = {5, 6, 10, 15, 10, 4, 23, 13, 8, 9};int m;m = FindMax2(arr, 0, 9);printf("m = %d\n", m);return 0;}
：冒泡排序（从小到大）；
//冒泡排序的递归实现：从小到大#include#include//3.两数比大小的具体实现//L为第一个元素位序，R为最后一个元素的位序；void Bubble(int arr[], int L, int R){int temp;//1.递归出口if (L == R)return;else{for (int i=L; i<=R-1; i++){if (arr[i] > arr[i+1]){temp = arr[i];arr[i] = arr[i+1];arr[i+1] = temp;}}//2.进行完一个完整的比较周期（第一轮比较之后最大数在最右边）之后，//数组就被分成了Bubble(arr, L, R-1)和arr[R]两个部分//3.把剩下的部分继续用递归实现Bubble(arr, L, R-1);}return;}int main(){int arr[10] = {5, 6, 11, 15, 10, 4, 23, 13, 8, 27};Bubble(arr, 0, 9);for (int i=0; i


上一篇：MATLAB教学_08影像处理一

下一篇：改进粒子滤波算计及其matlab实现