《数据结构》算法学习

《数据结构》算法--递归与数学归纳法

递归与数学归纳法有着本质上的联系：

首先来了解一下数学上常见的函数、数列与程序中的函数之间的相互关系：

通过图表可以看出，两种思维方式是互通的，程序思维可以依托数学思维方式来实现，使问题变得更容易理解。

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<10; i++)printf("%d ", arr[i]);printf("\n");return 0;
}

：求两数的最大公约数（思想：辗转相除法）

//求两数的最大公约数（辗转相除法，若最后的余数为零则最后的被除数为最大公约数）
#include
#include
int gcd(int a, int b){int r = a % b;/*两数相除：若余数为零，则被除数是最大公约数；若余数不为零，则它们的最大公约数即是被除数与余数的最大公约数；*///递归出口if (r == 0)return b;elsereturn gcd(b, r);
}int main(){int a, b;scanf("%d", &a);scanf("%d", &b);int g = gcd(a, b);printf("%d\n", g);return 0;
}