递归/递归函数

不明白为什么很多学校要从“汉诺塔”讲起，这玩意是真的绕。

（）

递归（函数）的概念：

调用自身来求解问题

不要过多考虑递归细节，宏观层面上的理解递归就行

（）

ps:总不能一直调用下去吧？必须要有一个边界

递归的关键：

1. 递归的结束条件（边界）

2. 递归函数的功能

3. 常识（推导公式）

递归的基本框架：

func(n){    if(n满足递归结束条件){        //结束处理        ···    }    else{        //一些处理，生成新的参数new_n        ···        func(new_n);       }}

递归示例：

1. 求阶乘

函数声明 int jiecheng(int n)

a. 确定功能，jiecheng(n)表示求解n!，返回计算结果。

b. 确定边界，当n=1时，n!结果为1，这是已知的。

c. 常识：n! = n*(n-1)!

int jiecheng(int n) {if (n == 1) { //递归边界（结束条件）return 1;}else {return n * jiecheng(n - 1); //jiecheng()就是一个求阶乘的函数，直接拿过来用，不细究其它东西}}

当然，边界不是唯一的，你也可以把边界设置为 n=3 , n!的结果为6，这是已知的

int jiecheng(int n) {if (n == 3) { //递归边界（结束条件）return 6; //此时，这个函数只能计算大于等于3的数的阶乘}else {return n * jiecheng(n - 1); //递归函数的功能      jiecheng(n - 1)就是(n-1)!的结果，n!=n*(n-1)!}}

2. 求最值

int findmax(int arr[],int l,int r) {if (l == r) {//边界：片段中只有一个数//结果：自己就是最大的return arr[l];}else if ((r-l) == 1) {//边界：片段中有两个数//结果：两者比较return arr[l] > arr[r] ? arr[l] : arr[r];}else {//分成左右两部分int mid = (l + r) / 2;//计算左半部分的最大值int left_max = findmax(arr, l, mid); //findmax()就是一个求最值的函数，我直接拿过来用就行，不考虑其它//计算右半部分的最大值int right_max = findmax(arr, mid + 1, r);//结果return left_max > right_max ? left_max : right_max;}}

函数声明 int findmax(int arr[], int l, int r);

a. 确定功能，findmax(arr, l, r)表示求解 数组arr的l到r范围内，最大的元素，返回结果。

b. 确定边界，当l==r时，只有一个数，显然arr[l]就是最大的。

                      当r==l+1时，只有两个数，进行一次比较，就可以知道谁最大

c. 常识：对于一个数组arr = [1,9,3,4,8]，将其拆分为左右两个数组arr_l = [1,9,3]，arr_r = [4,8]

              设数组arr的最大元素为A，arr_l的最大元素为B，arr_r的最大元素为C

              则A = max(B,C)