计算机算法中的递归法与选择排序法是什么？请细讲

递归是设计和描述算法的一种有力的工具，由于它在复杂算法的描述中被经常采用，为此在进一步介绍其他算法设计方法之前先讨论它。

能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解。

递归算法的执行过程分递推和回归两个阶段。在递推阶段，把较复杂的问题（规模为n）的求解推到比原问题简单一些的问题（规模小于n）的求解。例如上例中，求解fib(n)，把它推到求解fib(n-1)和fib(n-2)。也就是说，为计算fib(n)，必须先计算fib(n-1)和fib(n-2)，而计算fib(n-1)和fib(n-2)，又必须先计算fib(n-3)和fib(n-4)。依次类推，直至计算fib(1)和fib(0)，分别能立即得到结果1和0。在递推阶段，必须要有终止递归的情况。例如在函数fib中，当n为1和0的情况。

在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解，例如得到fib(1)和fib(0)后，返回得到fib(2)的结果，……，在得到了fib(n-1)和fib(n-2)的结果后，返回得到fib(n)的结果。

在编写递归函数时要注意，函数中的局部变量和参数知识局限于当前调用层，当递推进入“简单问题”层时，原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层，它们各有自己的参数和局部变量。

由于递归引起一系列的函数调用，并且可能会有一系列的重复计算，递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时，通常按递推算法编写程序。例如上例计算斐波那契数列的第n项的函数fib(n)应采用递推算法，即从斐波那契数列的前两项出发，逐次由前两项计算出下一项，直至计算出要求的第n项。

选择排序法 是对 定位比较交换法 的一种改进。在讲选择排序法之前我们先来了解一下定位比较交换法。为了便于理解，设有10个数分别存在数组元素a[0]～a[9]中。定位比较交换法是由大到小依次定位a[0]～a[9]中恰当的值（和武林大会中的比武差不多），a[9]中放的自然是最小的数。如定位a[0],先假定a[0]中当前值是最大数，a[0]与后面的元素一一比较，如果a[4]更大，则将a[0]、a[4]交换，a[0]已更新再与后面的a[5]～a[9]比较，如果a[8]还要大，则将a[0]、a[8]交换，a[0]又是新数，再与a[9]比较。一轮比完以后，a[0]就是最大的数了，本次比武的武状元诞生了，接下来从a[1]开始，因为状元要休息了，再来一轮a[1]就是次大的数，也就是榜眼，然后从a[2]开始，比出探花，真成比武大会了，当必到a[8]以后，排序就完成了。

下面给大家一个例子：

mai()

{

int a[10];

int i,j,t;

for ( i = 0; i < 10; i ++ ) scanf("%d",&a[ i ]); /*输入10个数，比武报名，报名费用10000￥ ^_^*/

for ( i = 0; i < 9; i ++ )

for ( j = i + 1; j < 10; j ++)

if ( a[ i ] < a[ j ] ) { t = a[ i ]; a[ i ] = a[ j ]; a[ j ] = t; } /*打不过就要让出头把交椅，不过a[ i ]比较爱面子，不好意思见 a[ j ]，让t帮忙*/

for( i = 0; i < 10; i ++) printf("%4d",a[ i ]); /*显示排序后的结果*/

}

好啦，罗嗦了半天总算把定位比较排序法讲完了，这个方法不错，容易理解，就是有点麻烦，一把椅子换来换去，哎～

所以就有了下面的选择排序法，开始的时候椅子谁也不给，放在一边让大家看着，找个人k记录比赛结果，然后发椅子。具体来讲呢就是，改进定位比较排序法，但是这个改进只是一部分，比较的次数没变，该怎么打还是怎么打，就是不用换椅子了。每次外循环先将定位元素的小标i值记录到K，认为a[k]是最大元素其实i=k还是a[ i ]最大，a[k]与后面的元素一一比较，该交换的也是也不换，就是把K的值改变一下就完了，最后在把a[k]与a[ i ]交换，这样a就是最大的元素了。然后进入下一轮的比较。选择排序法与定位比较排序法相比较，比的次数没变，交换的次数减少了。

下面也写个例子：

main()

{

int a[10];

int i,j,t,k;

for ( i = 0; i < 10; i ++ ) scanf("%d",&a[ i ]); /*输入10个数，比武报名，报名费用10000￥ ^_^*/

for ( i = 0; i < 9; i ++ )

{ k = i; /*裁判AND记者实时追踪报道比赛情况*/

for ( j = i + 1; j < 10; j ++)

if ( a[ k ] < a[ j ] ) k = j;

t = a[ i ]; a[ i ] = a[ k ]; a[ k ] = t; /* t 发放奖品*/

}

for( i = 0; i < 10; i ++) printf("%4d",a[ i ]); /*显示排序后的结果*/

}