很多同学苦于递归算法,最多问题是这个算法是如何想出来的,其实我认为最主要是找到规律,或者说找到解决问题的核心算法,以及递归的结束条件,我称为程序的出口条件!
例1:阶乘问题
long result(int n)
{
if (n <= 1)
return 1;
else
return n * result(n - 1);
}
可以看到阶乘问题是理解递归的最好例子,因为完整的概括了递归的过程
1.核心算法,也就是规律 n * result(n - 1),
2.结束条件是 if (n <= 1)
例2:归并排序
void merge_sort(int q[], int l, int r)
{
if (l >= r) return;
int mid = l + r >> 1;
merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
else tmp[k ++ ] = q[j ++ ];
while (i <= mid) tmp[k ++ ] = q[i ++ ];
while (j <= r) tmp[k ++ ] = q[j ++ ];
for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
1.核心规律,是假设当前已经分好了两部分,排好序了,需要考虑的问题,就是如何将两个数组合并成一个,
很多同学不理解为什么能这样假设,因为程序的解决是建立在假设之上的,这就需要看一下结束条件了。
2.结束条件,其实程序分解到最后就是有两个数字组成的最小集合,每一个单个数字肯定是有序的,要考虑的就是由两个数所组成的集合如何合并的问题,这就是程序的结束条件,程序能够解决这一结束条件,才能让之前的假设成立,所以完整的程序才能正常运行。
总的来说,虽然归并排序比阶乘要难很多,但是,基本思路是一样的,那就是找到规律,写好结束条件,剩下的递归过程就交给计算机处理了。