递归

何为递归

递归，就是在运行的过程中调用自己,一般情况下多为函数自己调用自己。

构成递归需具备的条件

1. 子问题须与原始问题为同样的事，且更为简单；
2. 不能无限制地调用本身，须有一种情况，可以简化为非递归状况处理,即递归的结束条件。

如何设计递归算法

1. 确定递归公式
2. 确定边界(结束)条件

关于递归的练习

1+2+3+...+n(1-n的累加)

• 常规做法

//使用for循环
function getSum(n){
    var sum=0;
    for(var i=1;i<=n;i++){
        sum+=i;
    }
    return sum;
}

• 递归实现

function getSum(n){
    if(n==1){
        return 1;
    }
    return getSum(n-1)+n;
}

求n个整数的积(1-n的阶乘)

• 传统做法

function getProduct(n){
    var product=1;
    for(var i=0;i<=n;i++){
        product*=n;
    }
    return product;
}

• 递归实现

function getProduct(n){
    if(n==1){
        return 1;
    }
    return getProduct(n-1)*n;
}

求n个整数的平均值

• 常规做法

function getEverage(n){
    var sum=0;
    for(var i=0;i<=n;i++){
        sum+=i;
    }
    return sum/n;
}

• 递归实现

function getEverage(n){
    if(n==1){
        return 1;
    }
    return (getEverage(n-1)*(n-1)+n)/n
}

已知：数列1,1,2,4,7,13,24,44,...求数列的第 n项

与斐波那契数列类似,需要先总结出数列的规律:前三个数累加的和为第四个数

function fiboo(n){
    if(n==1){
        return 1;
    }
    if(n==2){
        return 1;
    }
    if(n==3){
        return 2;
    }
    return fiboo(n-3)+fiboo(n-2)+fiboo(n-1);
}

快速排序

快速排序的思想是：先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边，再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1,处理结束.

var arr=[10,12,9,7,1];

/*
分析排序过程:
升序:
    基准值:9
    最终参与排序的数组:[10,12,7,1](因为需要从参与排序的数组中删除基准值)
    left:[7,1]:
        基准值:1
        最终参与排序的元素[7](因为需要从参与排序的数组中删除基准值)
        left:[]
        right:[7]
        最后结果:left+基准值+right=[]+[1]+[7]=[1,7]
    right:[10,12]
        基准值:10
        最终参与排序的元素[12](因为需要从参与排序的数组中删除基准值)
        left:[]
        right:[12]
        最后结果:left+基准值+right=[]+[10]+[12]=[10,12]

    最终排序结果:left+基准值+right=[1,7]+[9]+[10,12]=[1,7,9,10,12]
*/

function quickSort(arr){
    if(arr.length<=1){
        return arr;
    }
    //选出基准元素的索引
    var index=Math.floor(arr.length/2);
    //确定基准元素
    var n=arr[index];
    //从原数组删除基准元素
    arr.splice(index,1);
    var left=[],right=[];
    for(var i=0;i<arr.length;i++){
        if(arr[i]<=n){
            left.push(arr[i]);
        }else{  
            right.push(arr[i]);
        }   
    }
    return quickSort(right).concat([n],quickSort(left)); 
}

• 添加控制排序规则(升序/降序)逻辑

/*
    arr:参与排序的数组
    flag:控制排序规则,默认升序
*/
function quickSort(arr, flag = true) {
    if (arr.length <= 1) {
        return arr;
    }
    //选出基准元素的索引
    var index = Math.floor(arr.length / 2);
    //确定基准元素
    var n = arr[index];
    //从原数组删除基准元素
    arr.splice(index, 1);
    var left = [], right = [];
    for (var i = 0; i < arr.length; i++) {
        //升序
        if (flag) {
            if (arr[i] <= n) {
                left.push(arr[i]);
            } else {
                right.push(arr[i]);
            }
            
        } else {  //降序
            if (arr[i] >= n) {
                left.push(arr[i]);
            } else {
                right.push(arr[i]);
            }
        }
    }
    //升序
    if(flag){
        return quickSort(left).concat([n], quickSort(right));
    }else{  //降序
        return quickSort(left,false).concat([n], quickSort(right,false));
    }
    
}