【算法入门】——递归排序

递归的定义

递归做为一种算法在程序设计语言中广泛应用。在代码的世界中，一个程序如果调用自身，那它就是递归的。 更直接地说，递归就是把规模大的问题转化为规模小的相似的子问题来解决。特别地，在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一个方法，所以就产生了函数调用它自身的情况，这也正是递归的定义所在。格外重要的是，这个解决问题的函数必须有明确的结束条件，否则就会导致无限递归的情况。

关键要素

1. 明确的终止条件

从上面的概念中我们知道了递归就是自己调用自己。在实际过程中，一个函数不可能是无限重复调用的，它需要一个明确的终止调节来避免死循环。

2. 明确终止后要干什么

当你发现你的递归代码已经到了终止条件了，那你就必须做点什么了，不然这个递归就是毫无意义的。

3. 递归中重复的逻辑

递归问题必须可以分解为若干个规模较小、与原问题形式相同的子问题，这些子问题可以用相同的解题思路来解决。从程序实现的角度而言，我们需要抽象出一个干净利落的重复的逻辑，以便使用相同的方式解决子问题。

4.先递，再归

用递归实现排序

情景

• 一堆学生排队
• 根据身高，从高到矮依次排开
• 最矮的站最前面

思路

• 我们首先要找一个同学为参考目标（基准）
• 然后大喊，比他矮的去前面，高的去后面
• 然后重复择同学为基准，一直喊这句话。

提取要素

1. 终止条件

我们以某个同学为基准作为了参照，让所有人和他去比较，如果选中的那个人，已经是最小的了，没有人跟他进行比较了，那递归就终止了

2. 做什么

当然是选基准同学

3. 重复逻辑

重复喊话

排序代码分两部分

第一部分：取任意数组的最小值

首先JS内置了Math.min

Math.min(1,2)    //1
Math.min.call(null,1,2)
Math.min.apply(null,[1,2])

然后实现取数组内最小值

let min = (numbers) => {
    if (numbers.length > 2) {    
        return min(
            [numbers[0], min(numbers.slice(1))] 
        )
    } else {
        return Math.min.apply(null, numbers)     //当数组只有两个元素的时候可以直接进行判断
    }
}

如果声明一个数组 let array = [4,3,6,9]，那么代码实现的过程如下：

min([4,3,9,6])
=min([4,min([3,9,6])]) // 取出了number[0]，且后面的数组删除了第一个数（取出的那个数）
=min([4,min([3,min([9,6])])]) //min([8,2]),numbers.length<=2了，就可以直接比较了
=min([4,min([3,Math.main.apply(null,[9,6])])]) //6小于9，返回6
=min([4,min([3,6])])
=min([4,3])
=3

第二部分： 从小到大排序（sort）

let minIndex = (numbers) => numbers.indexOf(min(numbers)) // 取最小值的下标
let sort = (numbers) => {
    if (numbers.length > 2) {        //递归终止条件
        let index = minIndex(numbers)
        let min = numbers[index]        //选基准同学
        numbers.splice(index, 1)    
        return [min].concat(sort(numbers))    //重复喊话
    } else {
        return numbers[0] < numbers[1] ? numbers : numbers.reverse()
    }
}

继续沿用上面的 数组a ，代码实现结果如下

sort([4,3,9,6])
=[3]+sort([4,9,6])
=[3]+([4]+sort([9,6]))
=[3]+([4]+[6,9])
=[3]+([4,6,9])
=[3,4,6,9]

这就是先递，再归

优缺点

优点

1. 简洁

在树的前序，中序，后序遍历算法中，递归的实现明显要比循环简单得多

缺点

1、时间和空间的消耗比较大

递归由于是函数调用自身，而函数调用是有时间和空间的消耗的：每一次函数调用，都需要在内存栈中分配空间以保存参数、返回地址以及临时变量，而往栈中压入数据和弹出数据都需要时间，所以降低了效率。

2、重复次数多

递归中很多计算都是重复的，由于其本质是把一个问题分解成两个或者多个小问题，多个小问题存在相互重叠的部分，则存在重复计算，如fibonacci斐波那契数列的递归实现。

3、调用栈溢出

调用栈可能会溢出，其实每一次函数调用会在内存栈中分配空间，而每个进程的栈的容量是有限的，当调用的层次太多时，就会超出栈的容量，从而导致栈溢出。