数据结构学习<三> 递归及相关问题

递归是数学和计算机科学中的基本概念,与数学上我们熟悉的数学归纳法有异曲同工之妙,例如阶乘就可以由递归实现。

1
2
3
4
5
int factorial(int N)
{
if(N==0) return 1;
return N*(factorial(N-1));
}

递归函数满足两个基本属性:

  • 必须明确解决归纳基础。
  • 每一次调用,必须包含更小的参数值。

接下来主要介绍用到递归的问题或者算法

欧几里得算法

欧几里德算法又称辗转相除法,是指用于计算两个正整数a,b的最大公约数gcd。

gcd(a,b) = gcd(b,a mod b) (不妨设a>b 且r=a mod b ,r不为0)

1
2
3
4
5
6
//算法,求两个数A,B的最大公约数
int gcd(int A,int B)
{
if(B==0) return A;
return gcd(B,A%B);
}

对于欧几里得算法,递归的深度由参数的算数性质决定。

分治法求最大值

分治法可以把一个大小为N的问题分解为两个独立非空部分的递归函数,它递归调用自身进行求解的次数会少于N次
如果两部分的大小分别为k和N-K,那么递归函数调用的总数为

$$
T_N=T_k+T_{N-k}+1,N\geq1,且T_1=0
$$

可以由归纳法得到

$$
T_N=N-1
$$

所以用分治法求最大值,便是讲数据分成两组,分别求出最大值,然后再比较出较大的那个值

1
2
3
4
5
6
7
8
9
Item max(Item a[],int l,int r)//l:left,r=right,m=midle
{
Item u,v;int m=(l+r)>>1;
if(l==r) return a[l];
u=max(a,l,m);
v=max(a,m+1,r);
if(u>v) return u;
else return v;
}

汉诺塔问题

汉诺塔问题是递归的一个经典问题

汉诺塔:汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。

汉诺塔

汉诺塔很深刻的适配了递归的精神!

所有的递归其核心便是

  • 要解决一个大问题,我可以先做一个小事情
  • 做了一个小事情后,余下的是和之前大问题一样的知识规模小一些的问题
  • 最小的那个问题我很容易就解决了

这里解决汉诺塔问题就可以按上述思想来,千万就不要去细究递归具体的运行了

  • 如果要把一个N层汉诺塔从A搬到C,那么:
  • 如果前N-1层可以找别人搞定,咱只管搬第N层,会不会变得非常容易?这一下就简单了:这时当它只有两层就好了,先把前N-1层看作一个整体,把它搬到B;然后把最下面的第N层搬到C;然后再把前N-1层从B搬到C。
  • 如果只有一个盘子,那就直接A->C就可以了撒
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void hanoi(int n, char A, char B, char C)
{
if (n == 1)
{
cout << "把第 " << n << " 个盘子" << "from " << A << " to " << C << endl;
return;
}
hanoi(n - 1, A, C, B);
cout<< "把第 " << n << " 个盘子" << "from " << A << " to " << C << endl;
hanoi(n - 1, B, A, C);
}
int main(void)
{
hanoi(3,'A','B','C');
return 0;
}

下一次就讲讲动态规划中递归解决背包问题:)